3 ms·

I always took the Turing 'Halting problem' as a sortof proxy for the general unknowableness of complex programs. As in, 'halting' could have been substitued wit

I always took the Turing 'Halting problem' as a sortof proxy for the general unknowableness of complex programs. As in, 'halting' could have been substitued with 'somewhere in the program variable x gets set to 5' and you could still construct a program in which it would be impossible to prove whether or not x gets set to 5. And of course the proof of the Halting problem relies on the possibility of crafting programs that are deliberately hard to parse - something that may or may not happen in practice. And so for me it all boils down to 'complexity is complex'. Which is kindof obvious to anyone thats wokred on large programs but might not be so intuitively obvious in some other fields. And so thats why there's always bugs. However hard you try, there is so much complexity in a large bit of software that you can't ever squash them all. And parallel processing adds another layer of complexity for sure. But I dont see how worrying about the Halting Problem helps deal with that any better than some of the language constructs we've already seen.

mtklein 6y ago
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.
chriswarbo 6y ago
> 'halting' could have been substitued with 'somewhere in the program variable x gets set to 5' and you could still construct a program in which it would be impossible to prove whether or not x gets set to 5. Rice's theorem extends the Halting Problem in a very general way. The idea is that for any program 'foo', we can invent a new program 'bar; foo;' which will only execute 'foo' once 'bar' has halted. Since the halting problem is undecidable in general, and 'bar' can be any program, it's undecidable whether such a program will eventually execute 'foo'. Any property that depends on whether or not 'foo' gets executed is hence undecidable. However: there are many properties which don't depend on whether 'foo' will eventually be executed. For example 'does this program take more than 1000 steps to halt?' is decidable, since we can just run the program for up to 1000 steps to see if it halts or not. More subtley, we can check things about the syntax, e.g. 'does this program contain a call to the "LaunchTheMissiles" function?'. That's easy to decide by just looking at all of the tokens in the code. Of course, this doesn't tell us whether such a call would ever be reached, e.g. it would flag a program like if (false) { LaunchTheMissiles(); } else { ImplementWorldPeace(); } This program would never launch the missiles, but it's often enough to spot potential issues, even if our errors are overly-conservative. Such false-positives can be really annoying when we try to retro-fit such checks on to languages which weren't designed for them; e.g. trying to spot pointer errors in C code or potential nulls in Java code. In contrast, designing them into the language from the start can be really useful. For example, that's what type systems do. For example, consider the following code: String foo() { if (true) { return "hello"; } else { return 123; } } This is perfectly correct, since it claims to return a String and it will return a String. However, every type checker in the world will reject this program due to the mere presence of the 'return 123' branch. This is quite a common pattern in programming language research: problems which are undecidable in most languages can be made trivial by designing the language with that problem in mind. In this case their 'while' example in C is very illustrative: there's not enough information in the code to know which (if any) of the loop iterations rely on the previous ones having been executed first. The fact that it could rely on execution order means we can't safely parallelise it. In contrast, a call like 'map(something, myList)' implies that each element's processing is independent (hence why MapReduce is popular for parallelism!).
- 6y ago

mtklein 6y ago

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.

chriswarbo 6y ago

> 'halting' could have been substitued with 'somewhere in the program variable x gets set to 5' and you could still construct a program in which it would be impossible to prove whether or not x gets set to 5. Rice's theorem extends the Halting Problem in a very general way. The idea is that for any program 'foo', we can invent a new program 'bar; foo;' which will only execute 'foo' once 'bar' has halted. Since the halting problem is undecidable in general, and 'bar' can be any program, it's undecidable whether such a program will eventually execute 'foo'. Any property that depends on whether or not 'foo' gets executed is hence undecidable. However: there are many properties which don't depend on whether 'foo' will eventually be executed. For example 'does this program take more than 1000 steps to halt?' is decidable, since we can just run the program for up to 1000 steps to see if it halts or not. More subtley, we can check things about the syntax, e.g. 'does this program contain a call to the "LaunchTheMissiles" function?'. That's easy to decide by just looking at all of the tokens in the code. Of course, this doesn't tell us whether such a call would ever be reached, e.g. it would flag a program like if (false) { LaunchTheMissiles(); } else { ImplementWorldPeace(); } This program would never launch the missiles, but it's often enough to spot potential issues, even if our errors are overly-conservative. Such false-positives can be really annoying when we try to retro-fit such checks on to languages which weren't designed for them; e.g. trying to spot pointer errors in C code or potential nulls in Java code. In contrast, designing them into the language from the start can be really useful. For example, that's what type systems do. For example, consider the following code: String foo() { if (true) { return "hello"; } else { return 123; } } This is perfectly correct, since it claims to return a String and it will return a String. However, every type checker in the world will reject this program due to the mere presence of the 'return 123' branch. This is quite a common pattern in programming language research: problems which are undecidable in most languages can be made trivial by designing the language with that problem in mind. In this case their 'while' example in C is very illustrative: there's not enough information in the code to know which (if any) of the loop iterations rely on the previous ones having been executed first. The fact that it could rely on execution order means we can't safely parallelise it. In contrast, a call like 'map(something, myList)' implies that each element's processing is independent (hence why MapReduce is popular for parallelism!).

6y ago