Display of natural and recognizable languages ​​in a Turing finite machine

Question

I tried my best to find the answer to this theoretical question, even if it is not a programming question, I believe that it is really connected.

Suppose a Turing machine type cannot have more than 1000 squares. What would be the relationship between the set of these types of recognizable languages ​​and the set of normal recognizable languages.

Answer 1

If I understand your question correctly, you are talking about a machine like Turing, with a ribbon that is limited to some constant legnth elements (in your question 1000) of the final alphabet. The length of the tape is independent of the size of the input (which would be the case with the Automoton linear constraint).

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

• Additionally, the Turing machine has some internal states (suppose 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 a Turing machine with a tape of constant length using a conventional finite state machine.

• To build a final state machine, you will need to take all possible states of your limited Turing machine. This is a combination of the internal states of the machine (there are S of them) and the state of the tape (A ^T of them), so you get a finite state machine with S * A ^T. This is quite a lot, but theoretically we do not care about it - it is a constant.

So my answer is that your limited machine with constant Turing tapes can recognize the same languages ​​as the machine with the final state.

Answer 2

I think that what you are describing is closer to Linear Bounded Automoton than to a Turing machine. LBA can recognize context-sensitive languages.

Answer 3

Intuitively, I would think that your limited machines can recognize a strict subset of the languages ​​recognized in the learning process. To prove this, you will need to build a language that recognizes turing, so the most efficient turing machine that recognizes the language requires more than 1000 positions on its tape.

Answer 4

By definition, a “turing-like machine” with an infinite ribbon (for reasonably small infinity values) is not a “friction machine”.

In practice, such a limited machine will be difficult to calculate functions of any interest.