3 ms·

How do you generate the sequence H_0, H_1, ...? Specifically, is there a Turing machine G that can generate H_0, H_1, ..., onwards, perhaps taking in some inpu

by geofft 5y ago

How do you generate the sequence H_0, H_1, ...? Specifically, is there a Turing machine G that can generate H_0, H_1, ..., onwards, perhaps taking in some input along the way? If so, then you can construct a self-contained Turing machine Z that takes a machine M as input, which works as follows: it calls G to generate H_0, runs H_0 for a bit on M, then calls G to generate H_1, runs H_1 for a bit on M, and so forth. This is a single Turing machine which does not need external modification. Internally, it works by having an inner Turing machine that it modifies. But Z itself doesn't change. Then you can define M = "if Z(M): loop", call Z(M), and get your contradiction back. If no, then you've built a more-powerful-than-a-Turing-machine machine of some sort.

srcreigh 5y ago
Thanks so much! This is fun. I think, with your explanation, there's still a big handicap for the halting machine code. To illustrate.. If I were to say to you: Is the correct answer yes or no, considering that later I will reverse my answer, and enforcing that you can't later change your answer? It's like, okay, of course, with that model, you can never win. I don't think it reveals any limitation of your understanding, you just got pulled into a game that you can't win. The limitation that is put on the code and in your example too is, although the machine can take in extra input along the way, at a certain point the mathematician gets the last word. If you have G(H,M) which at each point gives you [0|1]:H', a more interesting question is if what happens if you define M = "if H(M)[0]: print H(M)[1] and then loop". Then, does the printed out H(M)[1](M) produce any contradiction? Hopefully I'm making sense here! Thanks again for engaging.
- srcreigh 5y ago
  I mixed up some things here... If you have G(G,M) which at each point gives you [0|1]:G', it's interesting to think of what happens if you define M = "if G(G,M)[0]: print G' = G(G,M)[1] then loop"... does G'(G',M) always produce a contradiction?

by geofft 5y ago

srcreigh 5y ago

Thanks so much! This is fun. I think, with your explanation, there's still a big handicap for the halting machine code. To illustrate.. If I were to say to you: Is the correct answer yes or no, considering that later I will reverse my answer, and enforcing that you can't later change your answer? It's like, okay, of course, with that model, you can never win. I don't think it reveals any limitation of your understanding, you just got pulled into a game that you can't win. The limitation that is put on the code and in your example too is, although the machine can take in extra input along the way, at a certain point the mathematician gets the last word. If you have G(H,M) which at each point gives you [0|1]:H', a more interesting question is if what happens if you define M = "if H(M)[0]: print H(M)[1] and then loop". Then, does the printed out H(M)[1](M) produce any contradiction? Hopefully I'm making sense here! Thanks again for engaging.

srcreigh 5y ago
I mixed up some things here... If you have G(G,M) which at each point gives you [0|1]:G', it's interesting to think of what happens if you define M = "if G(G,M)[0]: print G' = G(G,M)[1] then loop"... does G'(G',M) always produce a contradiction?