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- 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!