5 ms·

> Furthermore, there is literally no way to tell whether your program will ever actually terminate without actually executing it. This is technically not corre

> Furthermore, there is literally no way to tell whether your program will ever actually terminate without actually executing it. This is technically not correct, is it? Or at least phrased a bit poorly. Maybe replace "your" with "any given"?

m12k 6y ago
Correct, not all programs suffer from the Halting Problem.
- arc0 6y ago
  I think that's kind of a malformed sentence. Programs themselves do not suffer or not suffer from the halting problem, it is only a problem when considering the space of all programs.
  - andi999 6y ago
    I also think some programs can suffer from the halting problem. I mentioned above properties of the decimal reprensentation of pi (like is 123456 in pi)
  - domnomnom 6y ago
    It's not malformed, it's just incorrect. Additionally, the halting problem is about provability. That sort of imprecision of language needs qualifiers at least.
est31 6y ago
Yeah there are plenty of programs where you can tell whether they terminate or not. The proof that the halting problem is decidable has a self referential component and most programs aren't self referential like this, nor do they make any library calls to halting problem deciders :). I think it's OK to do this simlification in a simple post like this, but important to keep in mind that it's a simplification. To make it more concrete, if you take a bunch of heuristics like scanning for while(true) {}, scanning whether there are any loops at all, discarding primitive foreach loops that have a linear relationship to the input data amount, etc, you have built a rudimentary halting problem decider that has 3 outputs: "will halt", "won't halt", "I don't know". You can make it better with lots of research, SAT3 solvers, etc, but ultimately you will have to accept that there will always be programs that the decider will output "I don't know" for.
- opnitro 6y ago
  Indeed. Languages like idris have the `total` keyword that runs a halting checker on functions. Of course, as you mentioned, there are functions that might halt that it can't figure out. But it's pretty darn good.
- 3pt14159 6y ago
  The proof that Turing gave never really left me fully convinced. Surely if the Romans had "the answer that denies the former" then clearly some version of it is possible in software.
  - arc0 6y ago
    What part of Turing's proof do you find unconvincing?
- andi999 6y ago
  But you can have easy examples like does the decimal reprensentation of pi contain four zeros in a row. I think we dont know if it is true, so you wouldnt know if your algo stops if you dont run it (and it stops). No need for self referential programs.
deleted 6y ago
[deleted]
lmilcin 6y ago
Yes, this is not true. The law should be treated literally, in general case of all possible programs running with infinite amount of resources. If you take a program and you don't know anything about it and it has infinite amount of memory and you have to tell whether it executes or not, in general, it is not possible. On the other hand knowing a little bit about the program already can make this statement not apply. As a simple example, restricting amount of memory makes it possible to construct a very simple algorithm to tell whether the program terminates or repeats ad infinitum, in finite time and resources. Real life programs are even easier to work with. Consider a CPU that increments a separate register for every executed instruction and terminates when the register overflows. We can easily tell that every program running on that CPU has to terminate. As you see, it is rather silly to use general mathematical properties of programs and apply them to real life programs without considering for how real life programs are different from mathematical concepts. Real life programs are not spherical cows in vacuum, they don't have infinite time and memory to execute and the CPUs executing them are not perfect Turing machines.
- saalweachter 6y ago
  > As a simple example, restricting amount of memory makes it possible to build a very simple algorithm to tell whether the program terminates or repeats ad infinitum, in finite time and resources. I feel like "finite" is doing a lot of work there.
  - lmilcin 6y ago
    At this point we are still talking mathematical terms. So, read it the following way: Mathematically, you can construct a program that, using finite amount of steps and finite amount of memory tells whether another program terminates or not IF you know this other program has finite amount of memory to use. Obviously, we know that even with very small amount of memory this is going to take huge amount of time. Just look at Busy Beaver function to appreciate how quickly this grows with amount of available memory: https://en.wikipedia.org/wiki/Busy_beaver https://en.wikipedia.org/wiki/Busy_beaver Basically, Busy Beaver function tells how long a program, given an amount of memory, can execute and still terminate. This fantastic function is my favorite function if we ever play a game of "who can think a function that grows faster". As a corollary, since every real life program has finite memory, it is not possible to construct a non-terminating program that will not repeat its output. Knowing this you just construct a simple program that looks for cycle in the program state.
kevinmchugh 6y ago
The sentence has a link to the wikipedia article on the halting problem, which is a fine way of handling the exceptions.
jcfrei 6y ago
I think a better way to describe the halting problem would be: There isn't a program or algorithm of lower complexity which can prove that a specific program actually terminates.
dkersten 6y ago
Its absolutely incorrect. I've written a synchronous event-based programming system for a project where every single program was absolutely guaranteed to terminate. Yes, it wasn't fully general, since it didn't support unbounded loops, but it could run many types of programs and they always terminated. When you can make assumptions about a program and its inputs, the halting problem doesn't apply. I mean, just simple observation shows that if you can't make whether your program terminates a condition inside your program, then the halting problem ambiguity as stated can't apply -- you may still not be able to determine if it halts or not, but with enough constraints or assumptions that can be taken as true, you absolutely can know if your program halts or not without executing it.
commandlinefan 6y ago
> Maybe replace "your" with "any given"? I'd be more inclined to replace it with "any non-trivial" in this case.
- nickdrozd 6y ago
  That would also be false. There are many non-trivial programs that can proved to halt or proved not to halt.

m12k 6y ago

Correct, not all programs suffer from the Halting Problem.

arc0 6y ago
I think that's kind of a malformed sentence. Programs themselves do not suffer or not suffer from the halting problem, it is only a problem when considering the space of all programs.
- andi999 6y ago
  I also think some programs can suffer from the halting problem. I mentioned above properties of the decimal reprensentation of pi (like is 123456 in pi)
- domnomnom 6y ago
  It's not malformed, it's just incorrect. Additionally, the halting problem is about provability. That sort of imprecision of language needs qualifiers at least.

est31 6y ago

Yeah there are plenty of programs where you can tell whether they terminate or not. The proof that the halting problem is decidable has a self referential component and most programs aren't self referential like this, nor do they make any library calls to halting problem deciders :). I think it's OK to do this simlification in a simple post like this, but important to keep in mind that it's a simplification. To make it more concrete, if you take a bunch of heuristics like scanning for while(true) {}, scanning whether there are any loops at all, discarding primitive foreach loops that have a linear relationship to the input data amount, etc, you have built a rudimentary halting problem decider that has 3 outputs: "will halt", "won't halt", "I don't know". You can make it better with lots of research, SAT3 solvers, etc, but ultimately you will have to accept that there will always be programs that the decider will output "I don't know" for.

opnitro 6y ago
Indeed. Languages like idris have the `total` keyword that runs a halting checker on functions. Of course, as you mentioned, there are functions that might halt that it can't figure out. But it's pretty darn good.
3pt14159 6y ago
The proof that Turing gave never really left me fully convinced. Surely if the Romans had "the answer that denies the former" then clearly some version of it is possible in software.
- arc0 6y ago
  What part of Turing's proof do you find unconvincing?
andi999 6y ago
But you can have easy examples like does the decimal reprensentation of pi contain four zeros in a row. I think we dont know if it is true, so you wouldnt know if your algo stops if you dont run it (and it stops). No need for self referential programs.

deleted 6y ago

[deleted]

lmilcin 6y ago

Yes, this is not true. The law should be treated literally, in general case of all possible programs running with infinite amount of resources. If you take a program and you don't know anything about it and it has infinite amount of memory and you have to tell whether it executes or not, in general, it is not possible. On the other hand knowing a little bit about the program already can make this statement not apply. As a simple example, restricting amount of memory makes it possible to construct a very simple algorithm to tell whether the program terminates or repeats ad infinitum, in finite time and resources. Real life programs are even easier to work with. Consider a CPU that increments a separate register for every executed instruction and terminates when the register overflows. We can easily tell that every program running on that CPU has to terminate. As you see, it is rather silly to use general mathematical properties of programs and apply them to real life programs without considering for how real life programs are different from mathematical concepts. Real life programs are not spherical cows in vacuum, they don't have infinite time and memory to execute and the CPUs executing them are not perfect Turing machines.

saalweachter 6y ago
> As a simple example, restricting amount of memory makes it possible to build a very simple algorithm to tell whether the program terminates or repeats ad infinitum, in finite time and resources. I feel like "finite" is doing a lot of work there.
- lmilcin 6y ago
  At this point we are still talking mathematical terms. So, read it the following way: Mathematically, you can construct a program that, using finite amount of steps and finite amount of memory tells whether another program terminates or not IF you know this other program has finite amount of memory to use. Obviously, we know that even with very small amount of memory this is going to take huge amount of time. Just look at Busy Beaver function to appreciate how quickly this grows with amount of available memory: https://en.wikipedia.org/wiki/Busy_beaver https://en.wikipedia.org/wiki/Busy_beaver Basically, Busy Beaver function tells how long a program, given an amount of memory, can execute and still terminate. This fantastic function is my favorite function if we ever play a game of "who can think a function that grows faster". As a corollary, since every real life program has finite memory, it is not possible to construct a non-terminating program that will not repeat its output. Knowing this you just construct a simple program that looks for cycle in the program state.

kevinmchugh 6y ago

The sentence has a link to the wikipedia article on the halting problem, which is a fine way of handling the exceptions.

jcfrei 6y ago

I think a better way to describe the halting problem would be: There isn't a program or algorithm of lower complexity which can prove that a specific program actually terminates.

dkersten 6y ago

Its absolutely incorrect. I've written a synchronous event-based programming system for a project where every single program was absolutely guaranteed to terminate. Yes, it wasn't fully general, since it didn't support unbounded loops, but it could run many types of programs and they always terminated. When you can make assumptions about a program and its inputs, the halting problem doesn't apply. I mean, just simple observation shows that if you can't make whether your program terminates a condition inside your program, then the halting problem ambiguity as stated can't apply -- you may still not be able to determine if it halts or not, but with enough constraints or assumptions that can be taken as true, you absolutely can know if your program halts or not without executing it.

commandlinefan 6y ago

> Maybe replace "your" with "any given"? I'd be more inclined to replace it with "any non-trivial" in this case.

nickdrozd 6y ago
That would also be false. There are many non-trivial programs that can proved to halt or proved not to halt.