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.
Neither can terminate - DEADLOCK
According to you, this proves the SUCCESSOR FUNCTION is un-
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)
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)