2 ms·
From what I understand of Minsky's work, that isn't worst-case, it's the work required. You need to examine every possible state to get an answer. > even if su
by shakna 9y ago
From what I understand of Minsky's work, that isn't worst-case, it's the work required. You need to examine every possible state to get an answer.
> even if such a machine were to operate at the frequencies of cosmic rays, the aeons of galactic evolution would be as nothing compared to the time of a journey through such a cycle ...the magnitudes involved should lead one to suspect that theorems and arguments based chiefly on the mere finiteness the state diagram may not carry a great deal of significance. [Minsky, 1967]
Minsky's impression seems to be that this is the bare minimum amount of work required to solve the halting problem for a specific case.
- madez 9y agoIf a finite state machine is in a deadlock, i.e. a state that directly leads to itself no matter what, you trivially find the cycle. That is only a trivial example. Another example are programs that never jump backwards. There are many other functions where the halting problem is practically solveable. The question is, what are the problems that are impossible in a turing machine but practical in a real computer?