Re:Scooping the Loop Snooper (2000)
by bruce343434 on Friday March 25, 2022 @04:20AM
(#30799727)
No but I’m saying: computers are not turing machines because they are not infinite. So they must be finite automata.
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
Re:Scooping the Loop Snooper (2000)
by danielheath on Thursday March 24, 2022 @04:48PM
(#30795149)
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.
that part is understood.
a dripping faucet, for example - is it dripping at 10 drips per hour? or 5 drips per hour? did it stop dripping? no way to tell - the period between drops could be one moment longer than you observed - it could had dripped right after you stopped observing it.
this upper limit is called the busy beaver function. but it is only applicable to turing machines, which we don't build, because we don't have an infinite tape.
All finite automatons are guaranteed to halt, and do so in linear time. There is nothing to analyze the answer is always true.