Halting problem computability and diagonal slash

[Olfaction]

Hallo,

Maybe can someone please help me here;

I've been reading that there is no general Turing Machine (TM) for specifying whether or not a given TM will end its calculation. One could prove this claim by applying Cantor's diagonal argument to a plot exhibiting the output of all possible TMs when applied an infinite set of inputs.

See Penrose 1989 The Emperor's New Mind, chapter: the insolubility of Hilbert's Problem;

or

https://www.decodedscience.org/turing-machines-and-the-halting-problem/12672/3

The proof implies a hypothetic foolproof TM termed H (TMH), that indeed always gives a computable output to the question of whether a given TM halts or not (i.e. ''1'' if it does, ''0'' if it does not). The use of Cantor's diagonal slash applied to the output of TMH is then showed to lead to paradoxes, and one concludes the TMH cannot exist. All is well explained in the link.

My problem starts here,

Let say that instead of TMH, we have a TM that simply displays a ''0'' whenever a TM exceeds a fixed number of steps. Let’s term this Turing Machine TMH*. Then we go through the same processes, using the diagonal slash, and it seems to me, we come to the same conclusion, that TMH* couldn’t exist! However, it seems from common sense that TMH* is perfectly computable, predictable and deterministic and therefore can exist as a genuine Turing Machine.

Isn’t the use of the Diagonal Argument to argue against the existance of a general TMH inappropriate?

Doesn’t the ''paradoxal result'' instead tells us that two distinct computable processes can lead to two different sets of computable numbers, at yet those both set be infinite? I.e. there is distinct ''phases'' of infinite sets, and two infinite sets may be distinct from each other, as well regarding to their sizes? Indeed like Cantor's initial use of the diagonal slash…

That would mean, the TM doing the diagonal slash, say TMD, is not contained among the initial set of TMs, because it belongs to a distinct infinite set?

But then, all that has nothing to do with resolving the Halting Problem.

Where am I wrong?

Thank you for your help.

P.S. Sorry if some terms or expressions are misused here, I've made effort, but I am new to the field. I would be happy to try to clarify if needed.

 

 

[wtf]

On 9/7/2018 at 4:19 AM, Olfaction said:

The use of Cantor's diagonal slash applied to the output of TMH is then showed to lead to paradoxes ...

 

 

I haven't the bandwidth today to respond in detail. I noted this particular phrase, which is the point at which you stopped working hard to understand the proof and instead substituted handwaving. First, the proof is a diagonalization, but it's not the Cantor diagonal argument. Secondly. "lead to paradoxes," no. It leads to the conclusion that TMH can not in fact exist.

My suggested for you would be to go back to the proof of the unsolvability of the Halting problem; and no matter how long it takes you, go over ever single itty-bitty detail until you clearly understand the proof. Only then go forward with your new example, which frankly doesn't hold water at all. In short you are stopping well short of understanding right at the point where the work gets hard. You need to push through that and understand the proof.

[Olfaction]

Well Thank you for the terminology tips. The word ''paradoxe'' is used here to express that if we accepted that the halting testing TM was existing, the maths get paradoxal. if you assume TMH does'nt exists, then effectively there is no paradoxe.

I would appreciate some insights about how, when applying the same proof to a TMH* (that just defines non-halting for a TM  as exceeding a fixed amount of steps), one does'nt come with the conclusion that TMH* doesnt exist.

Thank you

Edited September 9, 2018 by Olfaction

[wtf]

7 hours ago, Olfaction said:

Then we go through the same processes, using the diagonal slash, and it seems to me, we come to the same conclusion, that TMH* couldn’t exist! However, it seems from common sense that TMH* is perfectly computable, predictable and deterministic and therefore can exist as a genuine Turing Machine.

From your OP:

> Then we go through the same processes, using the diagonal slash,

The fact that you refer to the proof of the noncomputability of the halting problem as the "diagonal slash" makes me think you don't understand the proof. I could be wrong but you are vague where precision is required.

> it seems to me, we come to the same conclusion, that TMH* couldn’t exist!

Have you an argument?

> However, it seems from common sense that TMH* is perfectly computable, predictable and deterministic

Likewise, "it seems from common sense" doesn't constitute a proof. You are missing all the details needed to have an argument here. 

The rest of your OP doesn't say anything meaningful. I don't want to pick on it sentence-by-sentence but if I got started at all that's where I'd end up. I honestly can't give constructive criticism because your post is all over the map and not particularly coherent. I urge you to take your argument to the next level of detail to help you sort out your thoughts. I don't doubt you have the kernel of some question in mind, I just don't know what it is. 

 

> Let say that instead of TMH, we have a TM that simply displays a ''0'' whenever a TM exceeds a fixed number of steps. Let’s term this Turing Machine TMH*. Then we go through the same processes, using the diagonal slash, and it seems to me, we come to the same conclusion, that TMH* couldn’t exist!

Ok ps -- here is some specific constructive criticism. You recall in the proof of the unsolvability of the Halting problem, we assume we have a solver for H, called TMh; Then we defined some NEW Turing machine TMx, say, in terms of TMh, and then we diagonalize and show that TMx can't in fact be a TM at all.

So in your scenario, we have TMh*. So what is your auxiliary function that you're using to get your impossibility result?

In other words, "Then we go through the same processes ..." is where your argument has a giant hole. What same process? You need to be very specific.

Edited September 10, 2018 by wtf

[uncool]

"Let say that instead of TMH, we have a TM that simply displays a ''0'' whenever a TM exceeds a fixed number of steps."

When you say a fixed number, do you mean that this one TM, say, checks if another TM goes longer than 1000 steps, outputting a 1 if it stops before then and a 0 otherwise?

 

[Olfaction]

Uncool -> Yes This is exactlly what I mean.

 

Edited September 10, 2018 by Olfaction

[Olfaction]

Thank you for your support.

< The fact that you refer to the proof of the noncomputability of the halting problem as the "diagonal slash" makes me think you don't understand the proof. I could be wrong but you are vague where precision is required.

Yes I knew the way I would express things will be problematic. That is why I put the link to a detail of the proof, and I thought this would avoid me expressing things wrong. I will try to express my understanding of the proof in my own words, as it helps to show whether I understand it or not. And then go on again with my question in simpler terms and avoiding alternative explanation.

This will be a lot based on Penrose’s 1989 The Emperor's New Mind, chapter: the insolubility of Hilbert's Problem;

We have Tn(m), where ‘n’ is the number of the Turing machine (TM), and (m) is the input.

Whenever Tn(m) doesn’t end its calculation, we express as: Tn(m) = □.

Now, we ‘assume’ we are provided with a TM ‘H’ that can tells us whether Tn(m) ends its calculation or not. Here what TMH does:

H (n;m) = 0 if Tn(m) = □,    and    H (n;m) = 1 if Tn(m) = stops.

We first imagine an infinite array, which lists all the outputs of all possible TMs acting on all the possible different inputs. The nth row of the array displays the output of the nth TM, as applied to the various inputs m = 0,1,2,3,4…:

n\m	…	0	1	2	3	4	5	6	7
…	…	□	□	□	□	□	□	□	□
0	0	0	0	0	0	0	0	0	0
1	1	1	1	1	1	1	1	1	1
2	0	2	0	2	0	2	0	2	0
3	0	□	0	□	0	□	0	□	0
4	0	□	1	□	2	□	3	□	4
5	1	1	1	□	□	1	1	1	1

Note: all the outputs are fictive and were chosen for their explicative meaningfulness: i.e. the ns are not real TM machine numbers, and the output are not accurate if applied to inputs ms.

We then apply to the whole table:

Tn(m) x H (n;m)

Which gives as all the actual inputs as from TMns exept that when this TM wasn’t to stop, the □ is replaced by a ‘0’ (hence the purpose of TMH)

n\m	…	0	1	2	3	4	5	6	7
…	…	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0
1	1	1	1	1	1	1	1	1	1
2	0	2	0	2	0	2	0	2	0
3	0	0	0	0	0	0	0	0	0
4	0	0	1	0	2	0	3	0	4
5	1	1	1	0	0	1	1	1	1

 

Here comes the Cantors diagonal slash in play, watch it picks up the numbers in fat and display new sequence.

n\m	…	0	1	2	3	4	5	6	7
…	…	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0
1	1	1	1	1	1	1	1	1	1
2	0	2	0	2	0	2	0	2	0
3	0	0	0	0	0	0	0	0	0
4	0	0	1	0	2	0	3	0	4
5	1	1	1	0	0	1	1	1	1

Says the machine that does the diagonal slash is termed TMD we would have:

D(n;m) x Tn(m) x H(n;m) = 0, 1, 2, 0, 0, 1, …

To which we add one

1+ (D(n;m) x Tn(m) x H(n;m)) = 1, 2, 3, 1, 1, 2, …

It is important to note at this point that according to Penrose, if we assume TMH exists, all the subsequent operations are perfectly computable.

The paradox arises, as if our array is to list all the outputs of all possible TMs acting on all the possible different inputs, then among of the outputs from the array should also figure our new sequence: 1, 2, 3, 1, 1, 2, …

Yet it cannot be so, for our new sequence differs from the first row in the first entry, from the second row in the second entry and so on. From this contradiction, one had proven that the TMH cannot exist. End of the proof.

Here now my question:

Say we repeat the same proof, but instead of using TMH, we use TMH*.

TMH*, is opposite to TMH, is well defined.

TMH* checks if another TM goes longer than 1000 steps, outputting a 1 if it stops before then and a 0 otherwise.

As an argument that this TMH* indeed exists its coding may look like that in Turing notation

if   Tn1 does        1.    00  ►  00R,     2.   01 ►131R

Which in text reads as: 1. If you are in  the internal state ‘0’ and see a 0 on the tape, then stay to internal state 0, leave a 0 on the tape, and move to right (R).

The coding TMH* (n1,m) would look like:

1.    00  ►  010R,     2.   01 ►130111R  

3.  Whenever you are in the internal state nn(output of the Tn1) followed by thousand ‘1’ then display 0 and stop.

This is clearly just a sketch but I’m sure any computer scientist would agree that such a ‘step counter’ TM exists?

Let’s then take our array again, and then make

Tn(m) x H* (n;m). It would look like previously, except with more 0s, as the criterion for what is a non-halting TM is much more restrictive.

n\m	…	0	1	2	3	4	5	6	7
…	…	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0
1	1	1	1	1	1	1	1	1	1
2	0	2	0	2	0	2	0	0	0
3	0	0	0	0	0	0	0	0	0
4	0	0	1	0	2	0	3	0	4
5	1	1	0	0	0	1	0	1	0

Again we go,

D(n;m) x Tn(m) x H*(n;m) = 0, 1, 2, 0, 0, 0, …

And

1+ (D(n;m) x Tn(m) x H(n;m)) = 1, 2, 3, 1, 1, 1, …

Again, the new sequence differs from the other sequences in the original array (the first row in the first entry, from the second row in the second entry and so on).

So we come to the conclusion TMH* also wouldn’t exist?

I hope now it is clearer and one may spot where I get wrong.

Thank you

[fiveworlds]

Quote

Isn’t the use of the Diagonal Argument to argue against the existance of a general TMH inappropriate?

Yes. A TM can use either a DFA or an NFA both are which are reducible to Boolean algebra all TMH has to do is show that a Boolean formula is satisfiable on a given input.

[wtf]

On 9/10/2018 at 4:43 AM, Olfaction said:

I hope now it is clearer and one may spot where I get wrong.

 

 

I prefer not to go through all that. Is that really Penrose's exposition? He's generally a very clear writer. In any event here's how I understand the proof. 

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. 

Now I admit I'm not an expert and I'm not familiar with all the variations on this proof. But the point is that in this version of the proof we define the hypothetical TMx, and show that it can't exist, showing that TMH can't exist. I'm asking you if you have an analogous construction for your idea.

Edited September 11, 2018 by wtf

[fiveworlds]

Quote

 

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. 

 

There's the problem it is an infinite loop. 

You can however define TMH that computes H(n, k) where n is a Boolean Algebra and k is a binary input.

Now I can encode TMH as n but not as k so the infinite loop never happens.

 

[wtf]

33 minutes ago, fiveworlds said:

There's the problem it is an infinite loop. 

You can however define TMH that computes H(n, k) where n is a Boolean Algebra and k is a binary input.

 

If you could supply the details for how to do that you would become famous, since you'd falsify a proof published by Alan Turing in 1936 and taught to undergrad CS students to this day.

Edited September 11, 2018 by wtf

[fiveworlds]

Quote

you would become famous,

I don't want to be though I like my privacy

It is easy to show though we can define what you were suggesting which is a description of tape n like so

input tape n = "
A(
  :nextState(boolean function)
  :halt(input == toBin(":halt(true and true)")) ||
  :halt(input == toBin(":halt(true and not false)")) ||
  :halt(input == toBin(":halt(not false and true)")) ||
  :halt(input == toBin(":halt(true or true)")) ||
  :halt(input == toBin(":halt(true or false)")) ||
  :halt(input == toBin(":halt(not false or false)")) ||
  :halt(input == toBin(":halt(not true or false)")) ||
  :halt(input == toBin(":halt(not false or true)")) ||
  etc ||
  :stuck(input == toBin("end of tape")
) {
  Get next input from k check if it validates as a transition from
  state A if not get next input from k.

  If there is no more inputs in k then switch to state "stuck"
}
HALT() {
  output "TM Halted"
}
STUCK() {
  output "TM STUCK"
}
";

inputTape k : ["input = 0000000", "input = etc"];

As you can see from state A there is only certain inputs that will cause TMH to halt which are labelled with :halt.

If input Tape k contains all the information in tape n then the input is too large to ever halt and will immediately become stuck.

Tape n will only halt on inputs such as toBin("halt(true and true)") etc.

[wtf]

1 hour ago, fiveworlds said:

I don't want to be though I like my privacy

 

That's interesting because I feel exactly the same way. I don't want to be famous. I have no idea why so many people do. 

I know that your idea is wrong, simply based on the fact that everyone regards Turing's proof as perfectly valid. Modern computer science is based on his ideas.

However as I indicated earlier, I'm not a CS expert. I know Turing's concepts and results, but I am not schooled in the technical details as a CS major major would learn them. I can't exactly see why your argument is wrong and can see I'd probably learn something from taking a run at it. I'll see if I can work through your idea this week. I'm a little busy with other projects at the moment but I'll put it in the queue.

TO @Olfaction, I wanted to explain why I have trouble with your exposition. You can see that @fiveworlds has stated an argument that is so specific, that it invites step-by-step understanding so as to refute it. It's wrong -- almost certainly, because it contradicts a well-known standard result -- but it's specific. I can follow it step by step ... because there are steps! And in working through @fiveworlds's presentation, I'll probably learn something or at least set myself a fun puzzle.

Whereas your exposition is handwavy. You say, "apply the same argument" but you don't say how to do it. You say that things are intuitively or clearly true, without presenting proof. It doesn't motivate me to work hard to understand you. I hope you will take this as constructive criticism. I am sure you have the kernel of some interesting idea, but you haven't provided enough detail for me to understand what your idea is. I encourage you to try to express your idea more clearly and succinctly. 

> 

:nextState(boolean function)

@fiveworlds, Are the halt() statements underneath that line supposed to be indented? Are they part of the function definition?

Also is this a notation you made up? Or is it a standard notation for TMs that I could read about somewhere, and if so where?

* ps another question. In HALT() you say to output "I'm halted." But you didn't produce an output. For a TM to be considered to have halted, it has to halt after a finite number of steps and output some number. Formally it's helpful to think of TMs as functions from the naturals to the naturals. It inputs a natural number and it has to output one. In fact you seem to be missing the very computation that you are required to make. Could that be a flaw? Not sure yet, just trying to understand your idea.

* ps -- another comment. Your program produces no output! You run it and it either halts or ends up in the stuck state (halting at an invalid state is regarded as not halting, in TM lore). Your function does nothing!! You run it and after a while it halts and outputs "I've halted," but it never computes anything at all! I think this is an aspect of your idea that needs to be fixed. You have to output a number. I mean you could just add the line "outout 47" to your HALT() function, but that's just the TM that computes the constant function 47. It certainly doesn't solve the halting problem. Help me out here, what is this notation supposed to do?

* ps another question (the forum software will merge my replies anyway so I'll just stick them here):

> :halt(input == toBin(":halt(true and not false)")) 

what are those inputs to the inner :halt? And if this suppose to be recursive, your :halt calls itself? With what arguments? What are true and false here? I think I'll stop asking any more questions till you clarify this notation.

 

Edited September 12, 2018 by wtf

[fiveworlds]

Quote

 

@fiveworlds, Are the halt() statements underneath that line supposed to be indented? Are they part of the function definition?

Also is this a notation you made up? Or is it a standard notation for TMs that I could read about somewhere, and if so where?

 

Nope you can use state transition tables too https://en.m.wikipedia.org/wiki/State_transition_table

Yes the halt statements are part of the input tape n they don't need to be there though. I left it there to show that you can use multiple state transitions on a tape.

eg.

A(
   :B(some Boolean expression)
)
B(
  :C(some Boolean expression)
 :A(some Boolean expression)
)
C(
  :halt(some Boolean expression)
)

So for instance this TM has 3 possible states. It starts in tape A and accepts some input set which will only result in a move to state B if the Boolean expression is true etc. The :states symbols work the similar to basic goto statements in assembly with an if condition.

For TMH we only stop executing if the string ":halt(some true Boolean expression)" is read by the TM or we run out of values to input from k.

Quote

I know that your idea is wrong, simply based on the fact that everyone regards Turing's proof as perfectly valid.

Who is everyone exactly?

[wtf]

1 hour ago, fiveworlds said:

Nope you can use state transition tables too https://en.m.wikipedia.org/wiki/State_transition_table

Yes the halt statements are part of the input tape n they don't need to be there though. I left it there to show that you can use multiple state transitions on a tape.

 

 

 

>  Nope you can use state transition tables too https://en.m.wikipedia.org/wiki/State_transition_table

I saw no syntax there that matched yours. Please supply a page describing your notation in detail.

> Yes the halt statements are part of the input tape n they don't need to be there though. I left it there to show that you can use multiple state transitions on a tape.

I don't know what that means. What are multiple state transitions on tape? The state transitions aren't on the tape in a TM. They're defined in the program.

Where do you get the boolean expressions? Your program doesn't express any logic that I can see. 

> Who is everyone exactly?

The CS community and all related communities such as physicists concerned with computability, mathematicians concerned with computability, philosophers, etc. And since the unsolvability of the Halting problem is intimately related to Gödel's incompleteness theorems. you have to overthrow modern mathematical logic too. And since Chaitin has proved incompleteness using complexity theory, there goes that too. You have a very large body of academic orthodoxy on the other side of your proposition. But that's not important. What's important is that I can't make heads or tails out of your notation. A TM consists of a program that acts on a tape one cell at a time. "If I'm in state X and the current symbol is Y then move the tape left or right, or leave it where it is, and optionally write the new symbols Z." I see none of that here. 

I didn't study CS so I don't know the details of DFA's so if you can dumb this down for me that would be great. I don't see anything being computed by your notation.

Edited September 12, 2018 by wtf

[Olfaction]

15 hours ago, wtf said:

Whereas your exposition is handwavy. You say, "apply the same argument" but you don't say how to do it. You say that things are intuitively or clearly true, without presenting proof. It doesn't motivate me to work hard to understand you. I hope you will take this as constructive criticism. I am sure you have the kernel of some interesting idea, but you haven't provided enough detail for me to understand what your idea is. I encourage you to try to express your idea more clearly and succinctly. 

I respect your criticism, and thank you for trying to help me.

but I kind of feel you did'nt read my explanation of the proof in my last post as you are refering to things I said in my first post again here? And because you said so explicitly you wont go through it? But to answer your first question yes, the way I put it here is pretty much word for word how it is in Penrose's book. Anyway, Thank you for  providing me another version of the proof, I will go through it. 

[Olfaction]

@wtf

In order to go further, I will use your own description of the proof to address my question again.

Say we take a very simple algorithm instead of H(n,m). One you will not reproach me of ''assuming it is intuitively computable''.

Say all what TMH(n,m) does is: if the n-th TM when applied the input m, outputs the number 3, then it outputs 1, and otherwise outputs 0.

We name this new TM ‘TMC’.

And here goes your proof again with some TMC instead of TMH:

 

 

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

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

Assume there is a TM, call it TMC, that computes C(n,n). 

Define another TM, called TMx, as follows. TMx(k) first runs TMC(k) to determine C(k,k). If C(k,k) = 1, meaning that the k-th TM outputs a 3 on k, then TMx(k) outputs a 6. 

If C(k,k) = 0, meaning that the k-th TM fails to output a 3 on k, then TMx(k) =  3.

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 C(x,x) = 1, meaning that TMC outputs a 3 on x, then TMx outputs a 6 on x.

But if C(x,x) = 0, meaning that TMH fails output a 3 on x, then TMx(x) = 3.

So TMx outputs a 3 on x if and only if it doesn't output a 3. That's a contradiction, showing that TMx can't exist. Therefore C is not in fact computable by a Turing machine. TMC can't exist. 

So how come using this proof we can show that any TM of the type X(n,m) = 1 or 0 doesn’t exist?

This proof recalls me a lot of Russell’s paradox…

 

Edited September 12, 2018 by Olfaction

[wtf]

5 hours ago, Olfaction said:

I respect your criticism, and thank you for trying to help me.

but I kind of feel you did'nt read my explanation of the proof in my last post as you are refering to things I said in my first post again here? And because you said so explicitly you wont go through it? But to answer your first question yes, the way I put it here is pretty much word for word how it is in Penrose's book. Anyway, Thank you for  providing me another version of the proof, I will go through it. 

You're right, I didn't read the second version. If Penrose wrote it I'd say the same to him as I did to you. But then again he's Sir Roger so probably I wouldn't! I'll take a look at your latest exposition when I get a chance. I should mention (again) that I'm relatively weak on computability theory so if someone who actually knows this stuff wants to jump in that would be great. I'm not really the right person for this.

[wtf]

On 9/12/2018 at 11:28 AM, Olfaction said:

@wtf

In order to go further, I will use your own description of the proof to address my question again.

Say we take a very simple algorithm instead of H(n,m). One you will not reproach me of ''assuming it is intuitively computable''.

Say all what TMH(n,m) does is: if the n-th TM when applied the input m, outputs the number 3, then it outputs 1, and otherwise outputs 0.

We name this new TM ‘TMC’.

And here goes your proof again with some TMC instead of TMH:

 

 

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

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

Assume there is a TM, call it TMC, that computes C(n,n). 

Define another TM, called TMx, as follows. TMx(k) first runs TMC(k) to determine C(k,k). If C(k,k) = 1, meaning that the k-th TM outputs a 3 on k, then TMx(k) outputs a 6. 

If C(k,k) = 0, meaning that the k-th TM fails to output a 3 on k, then TMx(k) =  3.

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 C(x,x) = 1, meaning that TMC outputs a 3 on x, then TMx outputs a 6 on x.

But if C(x,x) = 0, meaning that TMH fails output a 3 on x, then TMx(x) = 3.

So TMx outputs a 3 on x if and only if it doesn't output a 3. That's a contradiction, showing that TMx can't exist. Therefore C is not in fact computable by a Turing machine. TMC can't exist. 

Ok I think this looks correct up to the part I quoted. Then comes this:

> 

So how come using this proof we can show that any TM of the type X(n,m) = 1 or 0 doesn’t exist?

How does that follow? I think the point is that we can't compute whether the n-th TM halts on input n. Whether it halts output some particular value doesn't seem to make a difference, if I'm following this. If you can't compute whether an arbitrary TM halts period, you can't compute whether it halts with output k for any k. Is that what you're saying? 

[Olfaction]

On 19.9.2018 at 3:18 AM, wtf said:

How does that follow? I think the point is that we can't compute whether the n-th TM halts on input n. Whether it halts output some particular value doesn't seem to make a difference, if I'm following this. If you can't compute whether an arbitrary TM halts period, you can't compute whether it halts with output k for any k. Is that what you're saying? 

No my point is that ''TMC'' in my exemple has nothing to do with halting at all.

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

And using this proof we showed it cannot exist.

I actually tried to find a TM that would be ''obviously'' computable, in order to illustrate my problem about the proof.

Now you may argue that TMC does has to do with halting, as to know whether or not the n-th TM outputs a 3 or not, it has to know if it halts.

So I came with an other exemple:

 

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.

thank you for reading

 

Now if someone could show with other means, that TME actually is computable for any TM and and any input k, I think my point would be done.

Edited September 24, 2018 by Olfaction