A Turing Machine Question

+5 A:

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.

Anders Abel 2010-03-24 14:21:31

I don't think so - for LBA, the length of the tape is a linear function of the length of the initial input. However in this question, the input is a constant (which restricts the expressivity even further).

Tomas Petricek 2010-03-24 14:38:21

Tomas is correct. This is a DFA, not an LBA.

Brian Postow 2010-03-24 14:55:21

A:

By definition, a "turing-like machine" with a non-infinite tape (for reasonably small values of infinity) isn't a "turing machine".

In practice, such a limited machine would be hard pressed to compute functions of any interest.

msw 2010-03-24 14:23:39

You mean, such as computers as we know them today? (which also don't have infinite memory :-))

Joey 2010-03-24 14:25:19

@Johannes: Computers have generally had over 1K of memory for a long time, and generally make more efficient use of memory locations than Turing machines do of tape cells.

David Thornley 2010-03-24 14:31:28

@Johannes thus the "for reasonably small values of infinity" ;). But David pegged it.

msw 2010-03-24 14:45:15

@Johannes: Yes, in effect all computers are in fact DFAs. They have finite memory, and so a finite number of states. The fact that we PRETEND they have infinite (or at least "enough") memory, and so we can pretend that they are turing complete is merely a result of the fact that we don't need to match parenthesis on strings of length 10 Billion.

Brian Postow 2010-03-24 14:59:32

+1 A:

Intuitively, I would think that your limited machines could recognize a strict subset of turing-recognizable languages. To prove that, you'd need to construct a turing-recognizable language such that the most efficient turing machine that recognizes the language requires more than 1000 positions on its tape.

Peter Ruderman 2010-03-24 14:26:58

Easy example: if the automaton has N symbols and M states, a language that consists of all non-blank series of (N ^ 1000) * M + 1 symbols.

David Thornley 2010-03-24 14:30:33

+7 A:

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.

Tomas Petricek 2010-03-24 14:46:08

Great answer, but if the length of the tape is T and the size of the alphabet is A then the number of states the tape can encode is A ^ T, not T * A. It doesn't matter to the argument, since it's still finite, and therefore the automaton can only recognize regular expressions.

David Thornley 2010-03-24 15:04:11

@David Thornley: You're right - thanks for the correction! I'll fix the answer.

Tomas Petricek 2010-03-24 15:07:19

Great reasoning, you're answer is clearly the correct one.

Anders Abel 2010-03-24 15:46:39

normal turing machines can't recognize the same languages as a finite state machine ?

Hellnar 2010-03-24 16:21:57

@Hellnar: No, for example a language that contains all words consisting of n-times 0 followed by n-times 1 (e.g. `01`, `0011`, `000111`, ...) is not recognizable by finite state machines. You need to represent the number _n_ in some way, but that's not possible using finite number of states. This can be done by Turing machine (for example by marking _n_ cells of the tape when reading zeros).

Tomas Petricek 2010-03-24 18:35:36

ansaurus

tags:

views:

answers:

A Turing Machine Question

related questions