Notices
Results 1 to 7 of 7

Thread: Halting Problem Proof; a question.

  1. #1 Halting Problem Proof; a question. 
    New Member
    Join Date
    Sep 2018
    Posts
    2
    Hello everyone.

    Please someone help me on this:

    Alan Turing proved that there is no Turing Machine (TM) that could assert whether any other given TMs is going to end its calculation (Halting Problem). Meaning not that a TM couldn’t be successful at predicting halting of some other TMs, but that there is no existing TM that could predict halting for all the other TMs.

    Hence, whether or not a TM goes into an infinite loop, isn’t a computable question.

    What does computable means?

    Well, the only fact that we ‘’know’’ some process is non-computable i.e. not feasible by a ‘’single’’ or ‘’definable’’ TM, implies our brain has some functions that are not yet feasible from available machines.

    The question of computability is indeed;

    What are the theoretical limits to whatever could be done by a machine?

    Is the brain working like a TM?

    How one calculates computation time whit higher levels of complexity?

    Does Quantum computing allow effectuating operations that were thought to last overwhelm long with classical TMs?
    Etc.

    I could not access the original version of Turing’s proof, but here is a proof I read elsewhere:


    We enumerate all the TMs (there are lots of ways to do this, details are unimportant).

    We define a function H(n,m) that outputs 1 if the n-th TM halts on input m and 0 otherwise. We are interested in the restriction H(n, n). Note that H is definitely a function, we just don't yet know if it's computable.

    Assume there is a TM, call it TMH, that computes H(n,n).

    Define another TM, called TMX, as follows. TMX (k) first runs TMH(k) to determine H(k,k). If H(k,k) = 1, meaning that the k-th TM halts on k, then TMX (k) goes into an infinite loop.
    If H(k,k) = 0, meaning that the k-th TM fails to halt on k, then TMX (k) = 1.

    Now if TMX is in fact a Turing machine, it's on our list somewhere, say it's the x-th TM. What is TMX (x)? Well if H(x,x) = 1, meaning that TMH halts on x, then TMX goes into an infinite loop on x.
    But if H(x,x) = 0, meaning that TMH fails to halt on x, then TMX (x) = 1.

    So TMX halts on x if and only if it doesn't halt. That's a contradiction, showing that TMX can't exist. Therefore H is not in fact computable by a Turing machine. TMH can't exist.



    Ok so here is my problem about it.

    Say we have a TM that simply counts the number of steps on the tape of other TMs. Call it TMC.

    Say we apply TMD on the output of TMC.

    TMD is a time keeper TM, that outputs a ‘’0’’ whenever the output of TMC exceeds say 1000 steps and a ‘’1’’ otherwise.

    Is TMD x TMC actually computable?

    Let’s first assume so, to be concise.

    Let’s rename TMD x TMC = TME.

    Let’s undergo again the proof of the non-computability of TMH, but now applying to TME.


    Here it goes:


    We enumerate all the TMs (there are lots of ways to do this, details are unimportant).
    We define a function E(n,m) that outputs 1 if the n-th TM exceeds 1000 steps on input m and 0 otherwise. We are interested in the restriction E(n, n). Note that E is definitely a function; we just don't yet know if it's computable.

    Assume there is a TM, call it TME, that computes E(n,n).

    Define another TM, called TMY, as follows. TMY(k) first runs TME(k) to determine E(k,k). If E(k,k) = 1, meaning that the k-th TM exceeds 1000 steps on k, then TMY(k) goes into an infinite loop that contains more than 1000 steps.

    If E(k,k) = 0, meaning that the k-th TM exceeds 1000 steps on k, then TMY(k) = 1.

    Now if TMy is in fact a Turing machine, it's on our list somewhere, say it's the y-th TM. What is TMY(y)? Well if E(y,y) = 1, meaning that TME exceeds 1000 steps on y, then TMY goes into an infinite loop that contains more than 1000 steps on y.

    But if E(x,x) = 0, meaning that TME exceeds 1000 steps on y, then TMY(y) = 1.
    So TMY exceeds 1000 steps on y if and only if it doesn't exceeds 1000 steps. That's a contradiction, showing that TMY can't exist. Therefore E is not in fact computable by a Turing machine. TME can't exist.



    So did we just proved TME cannot exist?

    Do you agree with me TME is computable?

    Isn’t this proof doomed by Russel’s Paradox?

    It could prove anything because of its inner structure?

    Where am I wrong?

    Thank you.


    Reply With Quote  
     

  2.  
     

  3. #2  
    Forum Freshman
    Join Date
    Feb 2018
    Posts
    26
    How many steps to compute the largest prime? Is there a largest prime or do they go on forever? There is no proof of either. How can a computer compute a halt without a defined formula?

    Since the formula in the Turing is undefined, and since "any finite formula" can be that formula, even infinitely recursive formulas, there can be no computability of a Turing machine. That is to say a Turing machine can read out a "halt" if the formula halts in a finite time but it can't read out a "not halt" if the formula doesn't halt.

    Just because the brain, or a computer can't solve any, and every problem doesn't mean the brain, or a computer can't think. Thinking isn't defined that way.


    Reply With Quote  
     

  4. #3  
    Forum Ph.D.
    Join Date
    Jul 2008
    Location
    New York State
    Posts
    933
    Quote Originally Posted by doitright View Post
    How many steps to compute the largest prime? Is there a largest prime or do they go on forever? There is no proof of either. How can a computer compute a halt without a defined formula?
    There is no largest prime - proof goes back to Euclid.
    Reply With Quote  
     

  5. #4  
    Forum Freshman
    Join Date
    Feb 2018
    Posts
    26
    Quote Originally Posted by mathman View Post
    Quote Originally Posted by doitright View Post
    How many steps to compute the largest prime? Is there a largest prime or do they go on forever? There is no proof of either. How can a computer compute a halt without a defined formula?
    There is no largest prime - proof goes back to Euclid.
    Not absolutely rigorous. Depends on accepting limits as ends in approximations. Also irrelevant to the op question.
    Reply With Quote  
     

  6. #5  
    KJW
    KJW is offline
    Forum Professor
    Join Date
    Jun 2013
    Posts
    1,343
    Quote Originally Posted by doitright View Post
    Quote Originally Posted by mathman View Post
    There is no largest prime - proof goes back to Euclid.
    Not absolutely rigorous. Depends on accepting limits as ends in approximations.
    The proof that there is no largest prime is quite straightforward:

    Let P be the largest prime. Construct the number N that is one larger than the product of all the primes that are less than or equal to P. N is not divisible by any prime less than or equal to P. Therefore, N is either a prime larger than P, or is divisible by a prime larger than P. Either way contradicts that P is the largest prime, and therefore there is no largest prime.
    There are no paradoxes in relativity, just people's misunderstandings of it.
    Reply With Quote  
     

  7. #6  
    New Member
    Join Date
    Sep 2018
    Posts
    2
    Quote Originally Posted by doitright View Post
    How many steps to compute the largest prime? Is there a largest prime or do they go on forever? There is no proof of either. How can a computer compute a halt without a defined formula?

    Since the formula in the Turing is undefined, and since "any finite formula" can be that formula, even infinitely recursive formulas, there can be no computability of a Turing machine. That is to say a Turing machine can read out a "halt" if the formula halts in a finite time but it can't read out a "not halt" if the formula doesn't halt.

    Just because the brain, or a computer can't solve any, and every problem doesn't mean the brain, or a computer can't think. Thinking isn't defined that way.
    So what? You need no proof to resolve the halting problem? That might be true actually. But the fact is, there is this proof, that I described, one can find it in Textbook. I was hopping a comment that would justify its validity while pointing out the problem in my counter-exemple.

    Thank you.
    Reply With Quote  
     

  8. #7  
    Forum Freshman
    Join Date
    Feb 2018
    Posts
    26
    Quote Originally Posted by Olfraction View Post
    Quote Originally Posted by doitright View Post
    How many steps to compute the largest prime? Is there a largest prime or do they go on forever? There is no proof of either. How can a computer compute a halt without a defined formula?

    Since the formula in the Turing is undefined, and since "any finite formula" can be that formula, even infinitely recursive formulas, there can be no computability of a Turing machine. That is to say a Turing machine can read out a "halt" if the formula halts in a finite time but it can't read out a "not halt" if the formula doesn't halt.

    Just because the brain, or a computer can't solve any, and every problem doesn't mean the brain, or a computer can't think. Thinking isn't defined that way.
    So what? You need no proof to resolve the halting problem? That might be true actually. But the fact is, there is this proof, that I described, one can find it in Textbook. I was hopping a comment that would justify its validity while pointing out the problem in my counter-exemple.

    Thank you.
    Your problem takes a finite number of steps and if it doesn't halt it outputs a not halt. That's not a proof that follows the definition of the halting problem.

    If you understood the mathobabble you posted, or copy pasted, you should have known you flaw before posting.
    Reply With Quote  
     

Similar Threads

  1. Question about the Wirehead Problem in literature (and an eBook giveaway!)
    By Gudikan in forum Science-Fiction and Non-Fiction
    Replies: 2
    Last Post: March 15th, 2013, 03:27 PM
  2. Expansion problem question
    By Ascended in forum Physics
    Replies: 11
    Last Post: October 4th, 2012, 05:52 AM
  3. Replies: 58
    Last Post: August 11th, 2012, 06:57 AM
  4. Proof question... help lol
    By rhysboi1991 in forum Physics
    Replies: 3
    Last Post: August 2nd, 2010, 03:47 AM
  5. Pythagorean Theorem Question Problem
    By The P-manator in forum Mathematics
    Replies: 16
    Last Post: November 17th, 2006, 11:11 AM
Tags for this Thread

View Tag Cloud

Bookmarks
Bookmarks
Posting Permissions
  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •