Turing machine true/false questions

Question

There is a non-regular language that is recognized by a Turing Machine.

I believe the answer to this is true, because Turing machines can "count" computations and have a method to keep track of their previous operations.

A Turing Machine can have infinitely many states.

I believe this is true as well, but I'm not so certain why. I understand that the tape can be infinite, does this translate to an infinite number of states?

Answer 1

There is a non-regular language that is recognized by a Turing machine.

Yes, see the Chomsky hierarchy for more details.

A Turing machine can have infinitely many states.

It depends on what "states" mean:

• Turing machine can be represented by a graph which nodes are called states$^1$ and edges are called transitions. Here, this graph has to be finite, that is, Turing Machine can have only finitely many states$^1$.
• Turing machine has a tape of infinite length, and so if we put different values into cells of tape, then there are infinitely many different tapes. If we would regard such tape with values, current head position, etc. as state$^2$, then there would be infinitely many of those.

That being said, without additional context meaning state$^1$ is much more probable than state$^2$.

I hope this helps $\ddot\smile$

Answer 2

Imagine a Turing machine that has C cells that each can have S possible states. The number of states in the entire Turing machine is equal to $S^C$. If the Turing machine has an infinite number of cells, the Turing machine has $S^\infty$ states, which is equal to $\infty$.