4 ms·
You are talking about the worst-case. The worst-case is not very insightful. How probable is the worst-case? What about the average or median case? How hard are
by madez 9y ago
You are talking about the worst-case. The worst-case is not very insightful. How probable is the worst-case? What about the average or median case? How hard are the formerly unsolveable problems in practice?
- shakna 9y agoFrom 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?