4 ms·
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
by mythhabit 3y ago
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.
- vidarh 3y ago"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.
- mythhabit 3y agoYou 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.