# Thread: Halting Problem Proof; a question.

1. 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.

2.

3. 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.

4. Originally Posted by doitright
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.

5. Originally Posted by mathman
Originally Posted by doitright
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.

6. Originally Posted by doitright
Originally Posted by mathman
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.

7. Originally Posted by doitright
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.

8. Originally Posted by Olfraction
Originally Posted by doitright
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.