Hello everyone.

Please someone help me on this:

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

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.