4 ms·

Why does it need to be a real implementation of a turing machine? Why does the (hypothetical) turing machine need to be implementable? The thing is, if you ca

by gdp 17y ago

Why does it need to be a real implementation of a turing machine? Why does the (hypothetical) turing machine need to be implementable? The thing is, if you can contrive a halting oracle for a machine with a tape of length n, then I can contrive another turing machine with a tape of length n+1, and so on. The result is uh... the halting problem. And once again, I don't see why any of this even matters. Assuming the existence of some Turing machine (with infinite tape) is a garden-variety proof technique for these kinds of proofs. I still don't understand why you are insisting that it must be implementable? Computer memory is finite - does that mean we've solved the halting problem for all the programs we care about?

cjg 17y ago
If you don't have infinite memory (and who does) then there is no proof that a halting oracle does not exist. In fact, there is a proof that such an oracle does exist. So, yes, we can solve the halting problem where there is finite memory as long as our oracle is allowed more (perhaps much more) memory than that finite amount. The fact that the oracle is allowed more memory than the program obviates your n->n+1 objection. My point matters because the proof doesn't prove that you can't create a static parser for a perl program with only finite memory (in practice all perl programs). In other words, we shouldn't discourage someone from trying to build a static perl parser - it might well be possible. If you assume an infinite tape to prove a theorem then that theorem can only be applied in situations where an infinite tape is available.
- gdp 17y ago
  But you're describing a well-known intractable problem in computability. Finite-length tape doesn't make the problem any easier to solve, especially within the sorts of time limits that would be acceptable to users of static parsers. E.g. from Minsky (1967), referring to a machine with a million parts: "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" So the conclusion stands. If you presuppose an infinite tape, you get equivalence to the halting problem, and if you presuppose a finite tape beyond any non-trivial size, you get complete intractability.
  - cjg 17y ago
    Intractible doesn't mean impossible: perhaps someone will come up with a great new approach. The proof says nothing about what is possible with a finite tape. I hope you now feel that I have made a point that is, at least vaguely, relevant.

by gdp 17y ago

cjg 17y ago

If you don't have infinite memory (and who does) then there is no proof that a halting oracle does not exist. In fact, there is a proof that such an oracle does exist. So, yes, we can solve the halting problem where there is finite memory as long as our oracle is allowed more (perhaps much more) memory than that finite amount. The fact that the oracle is allowed more memory than the program obviates your n->n+1 objection. My point matters because the proof doesn't prove that you can't create a static parser for a perl program with only finite memory (in practice all perl programs). In other words, we shouldn't discourage someone from trying to build a static perl parser - it might well be possible. If you assume an infinite tape to prove a theorem then that theorem can only be applied in situations where an infinite tape is available.

gdp 17y ago
But you're describing a well-known intractable problem in computability. Finite-length tape doesn't make the problem any easier to solve, especially within the sorts of time limits that would be acceptable to users of static parsers. E.g. from Minsky (1967), referring to a machine with a million parts: "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" So the conclusion stands. If you presuppose an infinite tape, you get equivalence to the halting problem, and if you presuppose a finite tape beyond any non-trivial size, you get complete intractability.
- cjg 17y ago
  Intractible doesn't mean impossible: perhaps someone will come up with a great new approach. The proof says nothing about what is possible with a finite tape. I hope you now feel that I have made a point that is, at least vaguely, relevant.