3 ms·

I'm not sure that that's true. Some of the tricky cases for the halting problem boil down to the spiritual equivalent of trying to determine whether "this sent

• Gehinnn 6y ago
  Infinity can solve many problems. An infinite state machine can solve the halting problem! But I see the problem in my thoughts. If there are infinitely many cores with each core having a different id, after a finite amount of time only finitely many cores can distinguish itself, as the id gets arbitrarily long. If each core could process its id in O(1) time, you could decide the halting problem: each core would check whether the tm halts after id steps. Cores with higher ids would need to tick faster so that each core can process its id in O(1). Also, the halting problem does not exactly resemble "this sentence is false" (which is an obvious contradiction). It resembles more "the answer to this problem differs from the output of every turing machine". Such problems could be solved without contradiction by machines that cannot be simulated by turing machines! You don't even need infinity to create such machines. Turing machines with access to the halting oracle do the deed.