Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.


Math Forum » Discussions » sci.math.* » sci.math.independent

Topic: The MYTH of UNCOMPUTABLE FUNCTIONS
Replies: 3   Last Post: Jan 18, 2013 11:17 PM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Graham Cooper

Posts: 4,255
Registered: 5/20/10
Re: The MYTH of UNCOMPUTABLE FUNCTIONS
Posted: Jan 18, 2013 7:13 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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





Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.