2
$\begingroup$

All proofs for the undecidability of the halting problem seem to be based directly or indirectly on self-reference.

def g():
    if halts(g):
        loop_forever()

My question is: how can the input of a TM contain the TM itself and its input?

If the description of the TM has states and transitions, then it has more than its input therefore the input of the TM has infinite size because it contains both the TM and the input.

$\endgroup$
3
$\begingroup$

Try the following code instead:

def quote(s):
    return s.replace("'", "\\'")

def g():
    s = '''
def g():
    s = \'\'\'%s\'\'\'
    if halts(s %% quote(s)):
        while True:
            pass
'''
    if halts(s % quote(s)):
        while True:
            pass

If we add the following halting routine:

def halts(prog):
    print prog
    return False

then we can run g() and see that the input to halts is indeed the code for g():

>>> g()

def g():
    s = '''
def g():
    s = \'\'\'%s\'\'\'
    if halts(s %% quote(s)):
        while True:
            pass
'''
    if halts(s % quote(s)):
        while True:
            pass

A program that prints itself is called a quine. The corresponding result in computability theory is the recursion theorem, which ensures that (in a sense) a program can have access to its own source code.

$\endgroup$
  • $\begingroup$ Interesting. But why wouldn't that be considered as cheating? If I state "This statement is false" then my statement is finite on paper but its real form is infinite because the statement is allowed to reference itself. And the result is an inconsistent statement. But wouldn't adding an axiom that disallows circular references prove Gödel second incompleteness theorem is false and the halting problem is not undecidable because no TM would be allowed to reference itself and its own input and all recursions would have to be defined as explicit loops? $\endgroup$ – demanze May 13 at 9:03
  • $\begingroup$ My code is valid python, as you can check by executing it in python. So I don’t see where the cheating is. $\endgroup$ – Yuval Filmus May 13 at 9:07
  • $\begingroup$ Gödel’s incompleteness theorems are theorems with valid proofs. They can only be wrong if “mathematics” is inconsistent, which seems unlikely. You will just have to come to terms with their implications. $\endgroup$ – Yuval Filmus May 13 at 9:08
  • $\begingroup$ I don't mean the code is false. Like I said, "This statement is false" is a perfect valid way of using letters of the alphabet. Nothing physical will prevent me from constructing that statement. However, the statement is inconsistent, because if it is true then it is false. $\endgroup$ – demanze May 13 at 9:10
  • $\begingroup$ Philosophy is off-topic here, but you’re welcome to take it to that stackexchange site. $\endgroup$ – Yuval Filmus May 13 at 9:11
0
$\begingroup$

A description of a Turing machine contains: 1. the set of states (including initial & accepting & rejecting states) 2. the alphabet 3. the transition function

Note that we do not need to keep the input in the description. It's actually the same as any program you write, you don't write the actual input in your code. The input does not have its impact until runtime.

$\endgroup$
  • $\begingroup$ I don’t see how this answers the main difficulty, of the code mentioning the function being coded. $\endgroup$ – Yuval Filmus May 13 at 5:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.