Hacker News new | ask | show | jobs
by nyssos 521 days 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.
2 comments
Xcelerate 521 days 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

link
User23 521 days ago
It’s an LBA, a Linear Bounded Automata.
link
Tainnor 520 days 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).
link
User23 518 days ago
Arbitrarily long and infinite are very different things.
link
Tainnor 517 days ago
No, they're not.

The point is that a finite tape isn't enough for an LBA.

link
User23 517 days 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.

link
Tainnor 515 days 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.

link