5 ms·

Well, for a computer that is a finite state machine there are only finitely many states. So, in finite time the machine will either (a) halt or (b) return to a

Well, for a computer that is a finite state machine there are only finitely many states. So, in finite time the machine will either (a) halt or (b) return to an earlier state and, thus, be in an infinite loop. So, in this case can tell if the "program will stop" and, thus, solve "the halting problem". Uh, we also assume that before we start, we can look at the design of "the machine" and know how many states there can be and from the speed of the machine how many new states are visited each second. So, we will know how long we have to wait before we see either (a) or (b).

tgv 1y ago
Nobody is talking about a finite state machine in complexity. Its time complexity is n, and its space complexity is 0. The Halting Problem specifically pertains to Turing Machines.
- graycat 1y ago
  What I wrote is correct but does not address the traditional Turing Machine halting problem or solve it. The traditional halting problem is theoretical, i.e., not close to anything practical, and so is what I wrote. And I did not claim that what I wrote is a contribution to "complexity theory". The Turing Machine Halting Problem has long been standard computer science; from that it's common to conclude we can't tell if a program will stop. But that conclusion needs some theoretical assumptions, and my version is simpler and shows that we have to be careful drawing conclusions from the standard treatment.
  - tgv 1y ago
    > What I wrote is correct What your wrote is pretty much trivial, and not related to the topic of the article. It's also not practical, since the space needed to represent even a small program as an FSM is very large. Just try to write an FSM that reads binary coded 16 bit numbers, and has to find the maximum value. Now imagine sorting just 100 of them.
    - graycat 1y ago
      > What your wrote is ... not related to the topic of the article. The article was: The Halting Problem is a terrible example of NP-Harder and I wrote: > So, in this case can tell if the "program will stop" and, thus, solve "the halting problem". > "Trivial"? I never claimed the post was a significant contribution to computer science or complexity theory, and at most only a tiny fraction of posts at HN are such. Also, my post does not address the complexity theory question of P = NP. If what I wrote was "new, correct, and significant", then I should have sent it to a good computer science journal. I've published enough papers in good math and computer science journals to notice that the checks take a long time to arrive. I'm not in academics and never wanted to be. HN is not a journal of new, correct, and significant work in computer science. From responses in this thread, the post has proven to be at least curious and interesting to some of the HN audience.
brap 1y ago
But the halting problem is specifically for any kind of program. Otherwise you can just say that every codebase is smaller than X petabytes anyway so it’s always decidable.
- JohnKemeny 1y ago
  No, the halting problem doesn't hold when you have finite memory (as per OP's point). As OP says, after finitely many iterations (at most 2^n many), you have to be back at a previously seen state, and can terminate.
  - tromp 1y ago
    The halting problem requires both 1) unlimited length of programs whose halting behaviour is to be decided (so it can not be limited to program of at most 10 petabytes) 2) for those programs to have unlimited memory available You're arguing about point 2) in response to a post about point 1).
    - JohnKemeny 1y ago
      Well, the post I responded to was a respons to a post about point 2. I simply reiterated OP's point.
  - chriswarbo 1y ago
    Architectures like x86 can only address a finite amount of RAM, since they have a fixed word size (e.g. 64 bits). However, their memory is still unlimited, since they can read and write to arbitrary IO devices (HDDs, SSDs, S3, etc.); though those operations aren't constant time, they're O(sqrt(n)), since they require more and more layers of indirection (e.g. using an SSD to store the S3 URL of the address of ....)
  - deleted 1y ago
    [deleted]
  - deleted 1y ago
    [deleted]
Sankozi 1y ago
Yes, lots of these problems assume fantasy infinite world. Big O notation also suffers from this - it's almost useless for real world problems.
- suddenlybananas 1y ago
  >Big O notation also suffers from this - it's almost useless for real world problems. It's not the only way to optimize things but there's a reason no one sorts with bubble sort.
  - Sankozi 1y ago
    Yes bubble sort usually will take more time, but big O notation does not say that quick sort will be better for your real world problem. Complexity estimations or just benchmarks are much better at that. You should never limit yourself to big O notation when comparing algorithms.
    - suddenlybananas 1y ago
      >You should never limit yourself to big O notation when comparing algorithms. Sure, but it's still an incredibly useful tool for considering how your algo will scale.
  - LegionMammal978 1y ago
    Not quite bubble sort, but many recursive sorting implementations will switch to an O(n^2) algorithm like insertion sort once they reach a small number of elements. Simple but poorly-scaling methods usually have a place as base cases of hybrid algorithms. In other news, there's a reason no BLAS implementation multiplies matrices with Strassen's algorithm, and it's not that the people writing those are too dumb.
    - Al-Khwarizmi 1y ago
      Still, in quicksort, big O notation analysis is what tells you that you can further improve efficiency by leaving small subarrays unsorted and then performing a single call to insertion on the whole array at the very end, rather than one insertion call to sort each individual small subarray. This result is far from obvious without big O analysis. So still useful, even there.
Tainnor 1y ago
This approach suffers from two major problems: * It makes computability and complexity dependent on individual machines (now a program may halt on machine A, but not on machine B). For various reasons, we don't want that. * The entire state space of a single machine consists of all the registers, memory cells, etc. But keeping track of all states that have been visited before requires exponentially more space than the space that is actually available on the machine (because you're computing the powerset). So the machine itself can't solve its halting problem, only a much more powerful one can. Very often, impossibility results in infinitary mathematics translate back to "there's no reasonable way to do this" in actual practice where things are finite.
- Ukv 1y ago
  You wouldn't necessarily need to keep track of all states that have been visited before, to my understanding, just one extra state that you move along at half the speed (so it'll eventually also enter the loop, and then the state you're progressing at full speed will loop around and hit it). So 2X the memory and 1.5X the time/compute of the program on its own.
  - TheDong 1y ago
    Even simpler, you're just trying to figure out if it halts or not, not the exact length of the cycle, so you can do it with only a single counter for the total number of states. Say you have a machine with 128 bits of state, if it halts in 2^128 (roughly 340 undecillion) steps, that means it halts. If it's still going after 2^128 steps, then it'll keep going forever. So, to see if a 128 bit machine halts, you only need an extra 128 bits to count up 1-by-1 to 2^128. Sure, you also need a few thousand times the lifetime of the known universe just to count that high, but you know, It's O(2^128) instructions which means it's O(1). Good luck doing that on any machine with any real amount of memory of course. Really easy to write "just count to 2^128", but not so easy to do it.
  - Tainnor 1y ago
    This is interesting and I wasn't aware of this algorithm, thanks. I still maintain that it's practically infeasible to exhaust the entire state space of any modern machine.
userbinator 1y ago
More information on the algorithm to do so: https://en.wikipedia.org/wiki/Cycle_detection https://en.wikipedia.org/wiki/Cycle_detection
jerf 1y ago
That's great and all, but nobody is talking about physical computers here. Moreover, it's a useless observation in practice as well because the full exponentially-large state space necessary to represent such systems is not a useful formalism to approach computers with for any purpose, be it brutally practical or entirely theoretical. See https://news.ycombinator.com/item?id=23431703 https://news.ycombinator.com/item?id=23431703 for some previous comments I made on this, and some rough numbers base on computers that were already small 5 years ago and seem even smaller today. It is not useful to say "hey, that thing you're using has a finite state space and that finite state space is only 10^2,585,827,973 large!" It's not like you're going to run out.

tgv 1y ago

Nobody is talking about a finite state machine in complexity. Its time complexity is n, and its space complexity is 0. The Halting Problem specifically pertains to Turing Machines.

graycat 1y ago
What I wrote is correct but does not address the traditional Turing Machine halting problem or solve it. The traditional halting problem is theoretical, i.e., not close to anything practical, and so is what I wrote. And I did not claim that what I wrote is a contribution to "complexity theory". The Turing Machine Halting Problem has long been standard computer science; from that it's common to conclude we can't tell if a program will stop. But that conclusion needs some theoretical assumptions, and my version is simpler and shows that we have to be careful drawing conclusions from the standard treatment.
- tgv 1y ago
  > What I wrote is correct What your wrote is pretty much trivial, and not related to the topic of the article. It's also not practical, since the space needed to represent even a small program as an FSM is very large. Just try to write an FSM that reads binary coded 16 bit numbers, and has to find the maximum value. Now imagine sorting just 100 of them.
  - graycat 1y ago
    > What your wrote is ... not related to the topic of the article. The article was: The Halting Problem is a terrible example of NP-Harder and I wrote: > So, in this case can tell if the "program will stop" and, thus, solve "the halting problem". > "Trivial"? I never claimed the post was a significant contribution to computer science or complexity theory, and at most only a tiny fraction of posts at HN are such. Also, my post does not address the complexity theory question of P = NP. If what I wrote was "new, correct, and significant", then I should have sent it to a good computer science journal. I've published enough papers in good math and computer science journals to notice that the checks take a long time to arrive. I'm not in academics and never wanted to be. HN is not a journal of new, correct, and significant work in computer science. From responses in this thread, the post has proven to be at least curious and interesting to some of the HN audience.

brap 1y ago

But the halting problem is specifically for any kind of program. Otherwise you can just say that every codebase is smaller than X petabytes anyway so it’s always decidable.

JohnKemeny 1y ago
No, the halting problem doesn't hold when you have finite memory (as per OP's point). As OP says, after finitely many iterations (at most 2^n many), you have to be back at a previously seen state, and can terminate.
- tromp 1y ago
  The halting problem requires both 1) unlimited length of programs whose halting behaviour is to be decided (so it can not be limited to program of at most 10 petabytes) 2) for those programs to have unlimited memory available You're arguing about point 2) in response to a post about point 1).
  - JohnKemeny 1y ago
    Well, the post I responded to was a respons to a post about point 2. I simply reiterated OP's point.
- chriswarbo 1y ago
  Architectures like x86 can only address a finite amount of RAM, since they have a fixed word size (e.g. 64 bits). However, their memory is still unlimited, since they can read and write to arbitrary IO devices (HDDs, SSDs, S3, etc.); though those operations aren't constant time, they're O(sqrt(n)), since they require more and more layers of indirection (e.g. using an SSD to store the S3 URL of the address of ....)
- deleted 1y ago
  [deleted]
- deleted 1y ago
  [deleted]

Sankozi 1y ago

Yes, lots of these problems assume fantasy infinite world. Big O notation also suffers from this - it's almost useless for real world problems.

suddenlybananas 1y ago
>Big O notation also suffers from this - it's almost useless for real world problems. It's not the only way to optimize things but there's a reason no one sorts with bubble sort.
- Sankozi 1y ago
  Yes bubble sort usually will take more time, but big O notation does not say that quick sort will be better for your real world problem. Complexity estimations or just benchmarks are much better at that. You should never limit yourself to big O notation when comparing algorithms.
  - suddenlybananas 1y ago
    >You should never limit yourself to big O notation when comparing algorithms. Sure, but it's still an incredibly useful tool for considering how your algo will scale.
- LegionMammal978 1y ago
  Not quite bubble sort, but many recursive sorting implementations will switch to an O(n^2) algorithm like insertion sort once they reach a small number of elements. Simple but poorly-scaling methods usually have a place as base cases of hybrid algorithms. In other news, there's a reason no BLAS implementation multiplies matrices with Strassen's algorithm, and it's not that the people writing those are too dumb.
  - Al-Khwarizmi 1y ago
    Still, in quicksort, big O notation analysis is what tells you that you can further improve efficiency by leaving small subarrays unsorted and then performing a single call to insertion on the whole array at the very end, rather than one insertion call to sort each individual small subarray. This result is far from obvious without big O analysis. So still useful, even there.

Tainnor 1y ago

This approach suffers from two major problems: * It makes computability and complexity dependent on individual machines (now a program may halt on machine A, but not on machine B). For various reasons, we don't want that. * The entire state space of a single machine consists of all the registers, memory cells, etc. But keeping track of all states that have been visited before requires exponentially more space than the space that is actually available on the machine (because you're computing the powerset). So the machine itself can't solve its halting problem, only a much more powerful one can. Very often, impossibility results in infinitary mathematics translate back to "there's no reasonable way to do this" in actual practice where things are finite.

Ukv 1y ago
You wouldn't necessarily need to keep track of all states that have been visited before, to my understanding, just one extra state that you move along at half the speed (so it'll eventually also enter the loop, and then the state you're progressing at full speed will loop around and hit it). So 2X the memory and 1.5X the time/compute of the program on its own.
- TheDong 1y ago
  Even simpler, you're just trying to figure out if it halts or not, not the exact length of the cycle, so you can do it with only a single counter for the total number of states. Say you have a machine with 128 bits of state, if it halts in 2^128 (roughly 340 undecillion) steps, that means it halts. If it's still going after 2^128 steps, then it'll keep going forever. So, to see if a 128 bit machine halts, you only need an extra 128 bits to count up 1-by-1 to 2^128. Sure, you also need a few thousand times the lifetime of the known universe just to count that high, but you know, It's O(2^128) instructions which means it's O(1). Good luck doing that on any machine with any real amount of memory of course. Really easy to write "just count to 2^128", but not so easy to do it.
- Tainnor 1y ago
  This is interesting and I wasn't aware of this algorithm, thanks. I still maintain that it's practically infeasible to exhaust the entire state space of any modern machine.

userbinator 1y ago

More information on the algorithm to do so: https://en.wikipedia.org/wiki/Cycle_detection https://en.wikipedia.org/wiki/Cycle_detection

jerf 1y ago

That's great and all, but nobody is talking about physical computers here. Moreover, it's a useless observation in practice as well because the full exponentially-large state space necessary to represent such systems is not a useful formalism to approach computers with for any purpose, be it brutally practical or entirely theoretical. See https://news.ycombinator.com/item?id=23431703 https://news.ycombinator.com/item?id=23431703 for some previous comments I made on this, and some rough numbers base on computers that were already small 5 years ago and seem even smaller today. It is not useful to say "hey, that thing you're using has a finite state space and that finite state space is only 10^2,585,827,973 large!" It's not like you're going to run out.