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

IO is just state and can be represented on the tape. You can construct a machine for every conceivable input at every time during the execution and reason about them.


"while (gets()) {}" is undecidable because the "tape" is conceptually infinite.

So, no, you can not construct a machine for every conceivable input without imposing an artificial constraint on the input size.

Put another way: For every tape you construct and analyse, there is a tape one segment longer that might contain a symbol that can alter the outcome.


You can, theoretically, keep constructing machines for every input you need. Yes you are bounded, but you can say "this machine will halt for every input it can receive in the next 100 years", because you need to quantify the input in blocks of time.




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

Search: