Date: Jan 18, 2013 7:13 PM
Author: Graham Cooper
Subject: Re: The MYTH of UNCOMPUTABLE FUNCTIONS
On Jan 19, 5:40 am, George Greene <gree...@email.unc.edu> wrote:

> On Jan 12, 4:48 pm, Graham Cooper <grahamcoop...@gmail.com> wrote:

>

> > Turing's Halt Proof clearly proves that

>

> > HALT( program, input ) --> [yes/no]

>

> > is not a PURE FUNCTION!

>

> It's not OUR fault if you don't understand the proof.

> What the proof actually "clearly" proves ("clearly"

> in scare-quotes because it is unfortunately NOT clear to YOU)

> is that HALT( , ) is not A TURING MACHINE.

>

> >> How do you define "pure function"?

> > the output is determined by the input alone

>

> In the case of HALT ( , ), the output IS determined by the input

> alone. For every TMprogram, it either halts or it doesn't.

> ON EVERY input. Given the program, THE INPUT ALONE determines

> that truth-value. This is just a fact about TMs. Given this

> fact, it will follow that Halt( , ) is not a TM. But that does

> not stop it from being a pure function -- it's DEFINED as a pure

> function, so that is not even open to dispute.

>

Assume a process exists that runs any other process and ADDS 1.

Run 2 of these processes and cross the inputs.

Each process has it's one required argument.

P_1(P_2)

P_2(P_1)

Neither can terminate - DEADLOCK

According to you, this proves the SUCCESSOR FUNCTION is un-

computable!

STEP 1: ASSUME P HALTS GIVEN AN INPUT PROCESS THAT HALTS

STEP 2: P_1 HALTS (from 1)

STEP 3: P_2 HALTS (from 1)

STEP 4: P_1(P_2) should HALT (from 2 & 3)

CONTRADICTON

THEREFORE ADDING 1 TO A PROCESS' RESULT IN UN-COMPUTABLE

S: if stops(S) gosub S

G. GREENE: this proves stops() must be un-computable!

G. Cooper (BInfTech)

--

http://tinyURL.com/BLUEPRINTS-MATHEMATICS

http://tinyURL.com/BLUEPRINTS-HYPERREALS

http://tinyURL.com/BLUEPRINTS-QUESTIONS

http://tinyURL.com/BLUEPRINTS-POWERSET

http://tinyURL.com/BLUEPRINTS-THEOREM

http://tinyURL.com/BLUEPRINTS-PROLOG

http://tinyURL.com/BLUEPRINTS-FORALL

http://tinyURL.com/BLUEPRINTS-TURING

http://tinyURL.com/BLUEPRINTS-GODEL

http://tinyURL.com/BLUEPRINTS-PROOF

http://tinyURL.com/BLUEPRINTS-MATHS

http://tinyURL.com/BLUEPRINTS-LOGIC

http://tinyURL.com/BLUEPRINTS-BRAIN

http://tinyURL.com/BLUEPRINTS-PERM

http://tinyURL.com/BLUEPRINTS-REAL

http://tinyURL.com/BLUEPRINTS-SETS

http://tinyURL.com/BLUEPRINTS-HALT

http://tinyURL.com/BLUEPRINTS-P-NP

http://tinyURL.com/BLUEPRINTS-GUT

http://tinyURL.com/BLUEPRINTS-BB

http://tinyURL.com/BLUEPRINTS-AI