5 ms·

> Yet Turing machines are about as far from abstract mathematics as one can get, because you can actually build these things in our physical universe and observ

by nyssos 2y ago

> Yet Turing machines are about as far from abstract mathematics as one can get, because you can actually build these things in our physical universe and observe their behavior over time (except for the whole "infinite tape" part) The infinite tape part isn't some minor detail, it's the source of all the difficulty. A "finite-tape Turing machine" is just a DFA.

Xcelerate 2y ago
> is just a DFA Oh is that all? If resource bounded Kolmogorov complexity is that simple, we should have solved P vs NP by now! I debated adding a bunch of disclaimers to that parenthetical about when the infinite tape starts to matter, but thought, nah, surely that won’t be the contention of the larger discussion point here haha
User23 2y ago
It’s an LBA, a Linear Bounded Automata.
- Tainnor 2y ago
  No, an LBA in general doesn't have a finite tape. It still has an infinite tape, to accommodate arbitrary length inputs, it's just that the tape cannot grow beyond the length of its input (or a constant multiple of it, which is equivalent by the linear speedup trick).
  - User23 2y ago
    Arbitrarily long and infinite are very different things.
    - Tainnor 2y ago
      No, they're not. The point is that a finite tape isn't enough for an LBA.
      - User23 2y ago
        No they really are. Arbitrarily long means "pick a number any number." Infinite means, well infinite. And infinity is always bigger than "pick a number, any number." I suggest that you read Michael Sipser's Introduction to the Theory of Computation. It's absolutely lovely and an easy read, considering the subject matter. It will help you to understand cardinality (and many other things) in a pragmatic computing science context.
        Tainnor 2y ago
        It may be surprising to you that I've actually read a good portion of that text as well as other books on the subject. Or that I actually do understand what a cardinality is in a "pragmatic computing science context" (whatever that's supposed to mean). > Infinite means, well infinite There's a technical definition of "infinite cardinality" which is a bit more rigorous than "well infinite". If |S| > n for every natural number n, then S has infinite cardinality basically by definition. Why don't you try implementing an LBA simulator in your favourite programming language with a finite-sized array and tell me how it goes? Anyway, the original point was that a Turing Machine with a finite tape is an FSM. This is true (well, or more technically: it's equivalent to an FSM) because you can encode all possible configurations of the tape with a finite set of states and thus don't need any extra memory.

by nyssos 2y ago

Xcelerate 2y ago

> is just a DFA Oh is that all? If resource bounded Kolmogorov complexity is that simple, we should have solved P vs NP by now! I debated adding a bunch of disclaimers to that parenthetical about when the infinite tape starts to matter, but thought, nah, surely that won’t be the contention of the larger discussion point here haha

User23 2y ago

It’s an LBA, a Linear Bounded Automata.

Tainnor 2y ago
No, an LBA in general doesn't have a finite tape. It still has an infinite tape, to accommodate arbitrary length inputs, it's just that the tape cannot grow beyond the length of its input (or a constant multiple of it, which is equivalent by the linear speedup trick).
- User23 2y ago
  Arbitrarily long and infinite are very different things.
  - Tainnor 2y ago
    No, they're not. The point is that a finite tape isn't enough for an LBA.
    - User23 2y ago
      No they really are. Arbitrarily long means "pick a number any number." Infinite means, well infinite. And infinity is always bigger than "pick a number, any number." I suggest that you read Michael Sipser's Introduction to the Theory of Computation. It's absolutely lovely and an easy read, considering the subject matter. It will help you to understand cardinality (and many other things) in a pragmatic computing science context.
      - Tainnor 2y ago
        It may be surprising to you that I've actually read a good portion of that text as well as other books on the subject. Or that I actually do understand what a cardinality is in a "pragmatic computing science context" (whatever that's supposed to mean). > Infinite means, well infinite There's a technical definition of "infinite cardinality" which is a bit more rigorous than "well infinite". If |S| > n for every natural number n, then S has infinite cardinality basically by definition. Why don't you try implementing an LBA simulator in your favourite programming language with a finite-sized array and tell me how it goes? Anyway, the original point was that a Turing Machine with a finite tape is an FSM. This is true (well, or more technically: it's equivalent to an FSM) because you can encode all possible configurations of the tape with a finite set of states and thus don't need any extra memory.