Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



Re: The MYTH of UNCOMPUTABLE FUNCTIONS
Posted:
Jan 18, 2013 7:13 PM


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 scarequotes 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 truthvalue. 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 UNCOMPUTABLE
S: if stops(S) gosub S G. GREENE: this proves stops() must be uncomputable!
G. Cooper (BInfTech)  http://tinyURL.com/BLUEPRINTSMATHEMATICS http://tinyURL.com/BLUEPRINTSHYPERREALS http://tinyURL.com/BLUEPRINTSQUESTIONS http://tinyURL.com/BLUEPRINTSPOWERSET http://tinyURL.com/BLUEPRINTSTHEOREM http://tinyURL.com/BLUEPRINTSPROLOG http://tinyURL.com/BLUEPRINTSFORALL http://tinyURL.com/BLUEPRINTSTURING http://tinyURL.com/BLUEPRINTSGODEL http://tinyURL.com/BLUEPRINTSPROOF http://tinyURL.com/BLUEPRINTSMATHS http://tinyURL.com/BLUEPRINTSLOGIC http://tinyURL.com/BLUEPRINTSBRAIN http://tinyURL.com/BLUEPRINTSPERM http://tinyURL.com/BLUEPRINTSREAL http://tinyURL.com/BLUEPRINTSSETS http://tinyURL.com/BLUEPRINTSHALT http://tinyURL.com/BLUEPRINTSPNP http://tinyURL.com/BLUEPRINTSGUT http://tinyURL.com/BLUEPRINTSBB http://tinyURL.com/BLUEPRINTSAI



