Hacker News new | ask | show | jobs
by Tainnor 522 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.