Mapping of natural and recognizable languages in a finite Turing Machine

Question

I have been struggling to find an answer to this theoretical question, even tho it is not directly a programming question, I believe it is really related.

Assume a type of Turing machine which cannot have more than 1000 squares. What would be the relationship between the set of such type of recognizable languages and set of normal recognizable languages.

Answer 1

If I understand your question correctly, you're talking about Turing-like machine with a tape that is limited to some constant legnth (in your question 1000) elements of a final alphabet. The length of the tape doesn't depend on the input size (which would be the case for Linear Bounded Automoton).

• In this scenario, the number of states that you can represent by the tape is constant. More specifically, if the length of the tape is T and the size of the alphabet is A then the tape can encode only A^T states.

• Additionaly, the Turing machine has some internal states (let's say that the number of these states is S). At each point the machine has some internal state and some state of the tape, so we can simulate the Turing machine with constant-length tape using an ordinary finite state machine.

• To construct the finite state machine, you'll need to take all possible states of your limited Turing-machine. This is a combination of internal states of the machine (there is S of them) and the states of the tape (A^T of them), so you end up with a finite state machine with S*A^T states. That's quite a lot, but we don't care about that in theory - it is a constant.

So, my answer is that your limited constant-tape Turing machine can recognize the same languages as a finitie-state machine.

Answer 2

I think that what you are describing is more close to a Linear Bounded Automoton than to a Turing Machine. An LBA can recognize context-sensitive languages.