2 ms·

I'm sure someone more knowledgeable will point out the flaw, but couldn't Turing's machine definition be changed from infinite tape, to arbitrarily large tape,

• camel-cdr 4y ago
  Let me put it that way. Given any theoretical C implementation and a strictly confirming program (that doesn't do io) I can theoretically trivially solve the halting problem. Since the possible memory is constant for any given implementation, I can use the following algorithm: 1. Execute one instruction of the program 2. If the program terminated, goto 4. 3. insert entire program state into a hash table if it is already in the hash table, goto 5. otherwise, goto 1. 4. The Program terminates 5. The program never terminates The above algorithm solves the halting problem of any C program with a constant memory bound in finite time.