Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

By "detect loops" the parent meant "detect repetition of exact state". We have a fixed state machine. If we find ourselves in the same state, at the same location in the same tape, we must not halt because we will proceed in a loop indefinitely. If we have a finite tape, there are only finitely many states the entire system can occupy, so we must be able to exhaust them (or halt first, or loop first) in finite time.


Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: