13 ms·
"while (gets()) {}" is undecidable because the "tape" is conceptually infinite. So, no, you can not construct a machine for every conceivable input without imp
by 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.