3 ms·

An implication of your observation is that all the classical impossibility results, like for example the halting problem, concretized to the machine at hand bec

by madez 9y ago

An implication of your observation is that all the classical impossibility results, like for example the halting problem, concretized to the machine at hand become solveable theoretically, and maybe even practically. The turing machine abstraction is too idealized, I think.

snaily 9y ago
Have you seen how quickly busy beaver functions grow with the size of the program? It'd have to be a pretty restricted system to be tractable...
- userbinator 9y ago
  Those are still predicated on having an infinite tape. With finite storage, every program becomes a finite-state machine; and to "solve" the halting problem, one only needs to use the usual cycle-finding algorithms.
  - adrianN 9y ago
    With more than a handful of bits of state ever this restricted form of the halting problem is not solvable in general in practice. It's like saying "reading AES encrypted stuff is easy, you just have to try all keys"
- madez 9y ago
  What is the relation between busy beavers on turing machines and cycle finding in finite state machines?
shakna 9y ago
Theoretically yes, you're absolutely correct. See Minsky's work. Practically? No. Also from Minksy's work: A million binary states, results in 2 ^ 1,000,000 possible states that need to be examined. So, a 512kb program, needs an examination of about 4,000,000 states. However, that'd be a bare-metal program. Any examination would also need to include hosting code, such as the Operating System, and drivers being interacted with, and so on. It quickly blows out of proportion, and begins to become highly impractical, in similar ways to cryptographic algorithms. More than that, my examples are undercutting the scale - they're assuming program states and assembled programs are equivalent, but I don't think they are.
- 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 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 ago
      If 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?

by madez 9y ago

snaily 9y ago

Have you seen how quickly busy beaver functions grow with the size of the program? It'd have to be a pretty restricted system to be tractable...

userbinator 9y ago
Those are still predicated on having an infinite tape. With finite storage, every program becomes a finite-state machine; and to "solve" the halting problem, one only needs to use the usual cycle-finding algorithms.
- adrianN 9y ago
  With more than a handful of bits of state ever this restricted form of the halting problem is not solvable in general in practice. It's like saying "reading AES encrypted stuff is easy, you just have to try all keys"
madez 9y ago
What is the relation between busy beavers on turing machines and cycle finding in finite state machines?

shakna 9y ago

Theoretically yes, you're absolutely correct. See Minsky's work. Practically? No. Also from Minksy's work: A million binary states, results in 2 ^ 1,000,000 possible states that need to be examined. So, a 512kb program, needs an examination of about 4,000,000 states. However, that'd be a bare-metal program. Any examination would also need to include hosting code, such as the Operating System, and drivers being interacted with, and so on. It quickly blows out of proportion, and begins to become highly impractical, in similar ways to cryptographic algorithms. More than that, my examples are undercutting the scale - they're assuming program states and assembled programs are equivalent, but I don't think they are.

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 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 ago
    If 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?