4 ms·

Sure but halting problem is solvable for finite state machines.

• carlthome 3y ago
  Could you expand or provide a link to a good resource for me to understand this? If the judge program should say terminates yes/no and the program given is `while True: continue`, I guess the argument is that in the finite case, you could in principle just enumerate all programs that don't terminate and identify them as such?
  • jameshart 3y ago
    In principle, you can enumerate all possible memory states of the system and determine what the next memory state would be from each one (including multiple possible next states if you account for things like interrupts) Then you treeshake the unreachable parts of that directed graph from the start state, and look for closed loops in what remains.
    • carlthome 3y ago
      Makes sense! Thanks!