3 ms·
My computer has a finite state space, but I can still write programs where termination is not decidable.
by jagged-chisel 2y ago
My computer has a finite state space, but I can still write programs where termination is not decidable.
- arjvik 2y agoTermination is decidable, it's just that the finite program which decides if it terminates would take unfeasibly long to run.
- PhasmaFelis 2y agoCan you? It's been a long time since I studied Turing machines, but if a machine returns to an exact previous full state (of both the machine and the tape), then we know it will not terminate but loop forever; and a machine with a finite tape must return to a previous state in finite time if it doesn't terminate first. So a finite state machine will either terminate or begin to loop in finite time.
- Jerrrrrrry 2y agoAnyone can write a program to factor numbers into their factors. Just start at 1, and iterate until sqrt(x). Whats the big deal?