5 ms·

> This is a misunderstanding of the Turing machine model. The Turing machine is not designed to be a realistically implementable physical machine, and indeed th

> This is a misunderstanding of the Turing machine model. The Turing machine is not designed to be a realistically implementable physical machine, and indeed there are no details in Turing's paper on how such a physical machine could be achieved. I’ve read the paper. I think we just take different things from it, possibly because you have a background in mathematics? To me, the main takeaway (if I imagine reading it in 1936) is that a universal Turing machine is not all that complicated, and arouses the “I could build this thing”-intuition. That of course doesn’t mean that Turing intended it to be realizable, that’s not my point. But he appeals to an engineer’s intuition. It’s that intuitive link that’s valuable and unique IMHO. BTW, I think your takeaway is probably clearer in Gödel’s work.

eynsham 5y ago
The Turing machine has a tape of unbounded size so can’t be built simpliciter. Moreover although it turns out that that model of computation is very robust and sufficient for all purposes in physics (unless black holes or something allow hypercomputation) Turing does not really definitively show that and in a way that can’t be definitively shown. All we have is a lack of counterexamples (admittedly a very convincing one.) I don’t see why this intuition is that helpful generally either; Turing machines don't really help at an implementation level with modern engineering problems as far as I can tell. Most of the time you know that what you want to do is possible in finite time &c.—presumably the difficulty is doing what you want to do, and going via the Turing formalism would be a bit odd.
- bjornsing 5y ago
  > The Turing machine has a tape of unbounded size so can’t be built simpliciter. On the contrary, I think this is one of the advantages of Turing’s model: I can imagine standing there in my garage looking on as my universal Turing machine is running low on tape on the left side, and then simply attaching a new roll of fresh empty tape at the end, holding it as it is fed into the machine. :) It’s simply the least leaky abstraction of computation.
  - codeflo 5y ago
    Exactly this. Unbounded doesn't mean infinite, and people are sometimes confused by the distinction.
    - hardlianotion 5y ago
      Including me. What is the difference?
      - hansvm 5y ago
        The usual difference is just predicate ordering -- (1) for every program there exists a tape big enough vs (2) there exists a tape big enough for every program. In the first case, each individual (valid) program can get by with a tape of _some_ fixed length, but there's no bound on how big that requisite length might be. In the second case, since the tape requirements can be arbitrarily high you would need a legitimately infinite tape to service all possible programs. IMO the given example muddies the waters a bit by conflating the conceptual tape a given machine is running on (which might be infinite for non-halting programs) with the physical tape you've used so far (for which it suffices for such tape to be finite at any fixed moment in time, though the amount needed might grow unboundedly as time increases).
        codeflo 5y ago
        Note that tape usage typically depends on the input, so I would distinguish programs and computations (program + input).
      - Dylan16807 5y ago
        In a theoretical sense, an unbounded number is always finite. In a practical sense, turing machines don't voraciously consume tape. Adding extra feet of tape gives you an exponential increase in what you can compute. So if you set up a program to be reasonably judicious with its tape use, you can just say that if it reaches an end you pause it for a day, head to the shop, and buy another reel. Big computations take a lot of time anyway.

eynsham 5y ago

The Turing machine has a tape of unbounded size so can’t be built simpliciter. Moreover although it turns out that that model of computation is very robust and sufficient for all purposes in physics (unless black holes or something allow hypercomputation) Turing does not really definitively show that and in a way that can’t be definitively shown. All we have is a lack of counterexamples (admittedly a very convincing one.) I don’t see why this intuition is that helpful generally either; Turing machines don't really help at an implementation level with modern engineering problems as far as I can tell. Most of the time you know that what you want to do is possible in finite time &c.—presumably the difficulty is doing what you want to do, and going via the Turing formalism would be a bit odd.

bjornsing 5y ago
> The Turing machine has a tape of unbounded size so can’t be built simpliciter. On the contrary, I think this is one of the advantages of Turing’s model: I can imagine standing there in my garage looking on as my universal Turing machine is running low on tape on the left side, and then simply attaching a new roll of fresh empty tape at the end, holding it as it is fed into the machine. :) It’s simply the least leaky abstraction of computation.
- codeflo 5y ago
  Exactly this. Unbounded doesn't mean infinite, and people are sometimes confused by the distinction.
  - hardlianotion 5y ago
    Including me. What is the difference?
    - hansvm 5y ago
      The usual difference is just predicate ordering -- (1) for every program there exists a tape big enough vs (2) there exists a tape big enough for every program. In the first case, each individual (valid) program can get by with a tape of _some_ fixed length, but there's no bound on how big that requisite length might be. In the second case, since the tape requirements can be arbitrarily high you would need a legitimately infinite tape to service all possible programs. IMO the given example muddies the waters a bit by conflating the conceptual tape a given machine is running on (which might be infinite for non-halting programs) with the physical tape you've used so far (for which it suffices for such tape to be finite at any fixed moment in time, though the amount needed might grow unboundedly as time increases).
      - codeflo 5y ago
        Note that tape usage typically depends on the input, so I would distinguish programs and computations (program + input).
    - Dylan16807 5y ago
      In a theoretical sense, an unbounded number is always finite. In a practical sense, turing machines don't voraciously consume tape. Adding extra feet of tape gives you an exponential increase in what you can compute. So if you set up a program to be reasonably judicious with its tape use, you can just say that if it reaches an end you pause it for a day, head to the shop, and buy another reel. Big computations take a lot of time anyway.