3 ms·
A machine we have to today in isolation with no form of IO are not general Turing machines, but almost all of them do have that and so if you consider them in i
by vidarh 3y ago
A machine we have to today in isolation with no form of IO are not general Turing machines, but almost all of them do have that and so if you consider them in isolation rather than the full system (which would include all sources of inputs) the halting problem applies. E.g. code to the effect of "while gets() {}" will either halt or not halt depending on the input, but which isn't decidable without knowing or constraining that input.
We can certainly look for AGI that can do better at deciding the halting of decidable programs, but even for current computers the general halting problem is undecidable without adding artificial constraints.
- mythhabit 3y agoIO 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.