undefined | Better HN

0 pointsbruce3434344y ago0 comments

Yes it does. This is about turning the computer from a turing machine into a finite automaton. Finite automata can be analyzed for halting in finite time, turing machines can’t. And computers as we know them are not turing machines (which are by definition infinite) but they are state machines, and finite ones at that.

0 comments

Kranar4y ago

There is no way to turn a Turing Machine into a finite automaton.

All finite automatons are guaranteed to halt, and do so in linear time. There is nothing to analyze the answer is always true.

bruce343434OP4y ago

No but I’m saying: computers are not turing machines because they are not infinite. So they must be finite automata.

Jerrrry4y ago

exhaustively enumerating all inputs (and thus, outputs) to a program does, without infinite time or memory, turn it into an automaton.

you could then, since having gone over EVERY INPUT...conclude Yes or No, that it Does or Doesn't, HALT.

wtf am i missing

danielheath4y ago

Taking infinite time to determine whether it halts is not considered a valid answer.

When do you give up and decide it’s not going to terminate? Your answer will be wrong for any program which simply waits one second longer.

1 more reply

j / k navigate · click thread line to collapse