Hacker News new | ask | show | jobs
by jagged-chisel 619 days ago
My computer has a finite state space, but I can still write programs where termination is not decidable.
3 comments

Can 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.
Termination is decidable, it's just that the finite program which decides if it terminates would take unfeasibly long to run.
Anyone can write a program to factor numbers into their factors.

Just start at 1, and iterate until sqrt(x).

Whats the big deal?