4 ms·

Yep! That general version of the halting problem is Rice's Theorem, and that's exactly the thinking that proves it, by showing that if we did have an algorithm

Yep! That general version of the halting problem is Rice's Theorem, and that's exactly the thinking that proves it, by showing that if we did have an algorithm to determine any given non-trivial property of a program, we'd be able to use that algorithm to solve the halting problem. As for parallel processing, it can be fun to think about how things would work if you had a CPU with infinite cores. Any time your program wants to explore two or more options, you always have cores to explore those options in parallel. This sort of thinking is the root of the "non-deterministic" 'N' in "NP"... with infinite cores you can solve NP problems (including NP-complete ones) in polynomial time.

Gehinnn 6y ago
With infinitely many cores that are all connected to the same bus while each core has a unique id, you actually can solve the halting problem. You can basically brute force infinitely many inputs at once.
- mtklein 6y ago
  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 sentence is false" is true or false. It's not; it's neither. No infinite number of cores can help you there.
  - 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.
- onetoo 6y ago
  What you are describing is essentially a nondeterministic Turing machine. "What can you compute"-wise, NTMs are equivalent with TMs, and the halting problem still applies. NTMs are interesting when it comes to computation time, however. Open question: Can a TM compute in polynomial time what a NTM can compute in polynomial time?
- sabas123 6y ago
  What you describe would solve an NP problem. Since each NP has a successful path that answers the question in polytime, which must be taken by at least one core. However this does not help you with a program which would loop infinitely.
- jlouis 6y ago
  This doesn't work. If none of your tms halt you don't know if they would in a little while. You can simulate this by making a tm which runs 1 step of each machine at a time. This also hints at the equivalence other people have spoken of.
  - Gehinnn 6y ago
    The thing is that if infinite cores each perform 1 distinct step, the entire computer does infinitely many steps in one step. You cannot simulate this with a turing machine in finitely many steps. The problem is though, that even if each core has a distinct id, infinite cores can only perform distinct steps if the memory model uses unbounded cells. Otherwise almost all cores would do the same step.

Gehinnn 6y ago

With infinitely many cores that are all connected to the same bus while each core has a unique id, you actually can solve the halting problem. You can basically brute force infinitely many inputs at once.

mtklein 6y ago
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 sentence is false" is true or false. It's not; it's neither. No infinite number of cores can help you there.
- 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.
onetoo 6y ago
What you are describing is essentially a nondeterministic Turing machine. "What can you compute"-wise, NTMs are equivalent with TMs, and the halting problem still applies. NTMs are interesting when it comes to computation time, however. Open question: Can a TM compute in polynomial time what a NTM can compute in polynomial time?
sabas123 6y ago
What you describe would solve an NP problem. Since each NP has a successful path that answers the question in polytime, which must be taken by at least one core. However this does not help you with a program which would loop infinitely.
jlouis 6y ago
This doesn't work. If none of your tms halt you don't know if they would in a little while. You can simulate this by making a tm which runs 1 step of each machine at a time. This also hints at the equivalence other people have spoken of.
- Gehinnn 6y ago
  The thing is that if infinite cores each perform 1 distinct step, the entire computer does infinitely many steps in one step. You cannot simulate this with a turing machine in finitely many steps. The problem is though, that even if each core has a distinct id, infinite cores can only perform distinct steps if the memory model uses unbounded cells. Otherwise almost all cores would do the same step.