3 ms·

Can Turing machines invent Turing machines?

by yters 8y ago

adrianN 8y ago
I don't think you can give a sufficiently precise definition of "invent" to answer this question without being at odds with the intuitive understanding of "invent" that people normally hold. Turing machines can definitely search through the space of Turing machines and find some specific ones. For example that's what compilers do all day. They get a description of a Turing machine M1 written in language A and then produce a different Turing machine M2 that has the same semantics a M1, but is described in language B and is faster than M1 (that's what the optimizer does). Most people wouldn't call this "inventing" though (I would).
- yters 8y ago
  It isn't so much coming up with the specific operations, but the realization that TMs can emulate every other machine, i.e. the Church-Turing thesis. This seems to be beyond the capability of TMs as it ventures into the domain of the halting problem.
  - adrianN 8y ago
    Solving the Halting problem requires you to decide for all TMs whether they halt or not. Nothing is preventing you from deciding it for a useful subset of TMs. For example deciding it for all TMs that have an encoding that uses fewer bits than the number of atoms in the observable universe is totally possible. There are also infinite families of TMs for which you can solve the halting problem. Again, a lot of what compilers do sounds like it would require solving the halting problem, when in fact it doesn't because they only handle a subset of all possible cases.
    - yters 8y ago
      The parent article discusses the idea of a partial halting oracle (PHO), which decides for an undecidable subset of problems. A TM cannot meet this requirement, by definition. It seems like humans are in the category of PHOs.
      - adrianN 8y ago
        There is no proof that human brains are capable of deciding uncomputable sets and really no reason to believe that they should be able to.
        yters 8y ago
        That's a bit of a tangent. Here we were discussing whether the concept itself makes sense. But, as for empirical evidence, max entropy + Bayesian hypothesis selection makes the PHO hypothesis much more plausible than the TM hypothesis.

Can Turing machines invent Turing machines?

by yters 8y ago

Can Turing machines invent Turing machines?

I don't think you can give a sufficiently precise definition of "invent" to answer this question without being at odds with the intuitive understanding of "invent" that people normally hold. Turing machines can definitely search through the space of Turing machines and find some specific ones. For example that's what compilers do all day. They get a description of a Turing machine M1 written in language A and then produce a different Turing machine M2 that has the same semantics a M1, but is described in language B and is faster than M1 (that's what the optimizer does). Most people wouldn't call this "inventing" though (I would).

yters 8y ago
It isn't so much coming up with the specific operations, but the realization that TMs can emulate every other machine, i.e. the Church-Turing thesis. This seems to be beyond the capability of TMs as it ventures into the domain of the halting problem.
- adrianN 8y ago
  Solving the Halting problem requires you to decide for all TMs whether they halt or not. Nothing is preventing you from deciding it for a useful subset of TMs. For example deciding it for all TMs that have an encoding that uses fewer bits than the number of atoms in the observable universe is totally possible. There are also infinite families of TMs for which you can solve the halting problem. Again, a lot of what compilers do sounds like it would require solving the halting problem, when in fact it doesn't because they only handle a subset of all possible cases.
  - yters 8y ago
    The parent article discusses the idea of a partial halting oracle (PHO), which decides for an undecidable subset of problems. A TM cannot meet this requirement, by definition. It seems like humans are in the category of PHOs.
    - adrianN 8y ago
      There is no proof that human brains are capable of deciding uncomputable sets and really no reason to believe that they should be able to.
      - yters 8y ago
        That's a bit of a tangent. Here we were discussing whether the concept itself makes sense. But, as for empirical evidence, max entropy + Bayesian hypothesis selection makes the PHO hypothesis much more plausible than the TM hypothesis.