# Why is the complete state of a turing machine representable by a finite word?

At the moment I'm just reading through this article on the word problem for groups (https://projecteuclid.org/euclid.bams/1183548590), and I'm wondering about a certain snippet.

On page 40 the article describes a word that can encode the state of a turing machine, namely $S_{k_{u}}...S_{k_{1}}q_{i}S_{j_{1}}...S_{j_{v}}$ where $S_{k_{u}}...S_{k_{1}}S_{j_{1}}...S_{j_{v}}$ is the tape expression, $q_{i}$ is the current internal state of the turing machine, and $S_{j_{1}}$ is the currently scanned symbol.

I'm just wondering why this word is necessarily finite. Why can't the input of the turing machine have an infinite amount of non-zero characters?

• Welcome on CS.SE. Note that we prefer plain text to text-as-an-image. When asking, one is expected to cut & paste the text (and possibly format the formulas using MathJax). – chi Apr 27 '18 at 10:34
• Ah, no problem, I'll quickly fix that up now – user3201708 Apr 27 '18 at 10:38
• Awesome, I've just changed it now, be sure to tell me if there's anything else I need to do to make this question better. – user3201708 Apr 27 '18 at 10:45
• I think it is OK now. It is self-contained: the link is a bonus -- useful, but the question can be answered even without accessing the link. It is short and to the point, which is always a good thing. – chi Apr 27 '18 at 10:48

I'm just wondering why this word is necessarily finite. Why can't the input of the turing machine have an infinite amount of non-zero characters?

No, it can not.

When the Turing machine starts, the tape contains the input (a finite-length word) followed by an infinite amount of blank symbols (often written as #). It is common to simply omit the trailing infinitely many blanks, and just represent a finite prefix instead, adding blanks as needed when the head moves right past the end of the tape.

When the machine runs, in each step it can at most (over-)write over one tape symbol, and move right by at most one position. This is an essential feature of any Turing machine.

Hence, after finitely many steps, we still have a finite amount of non-blank symbols. The tape again contains infinitely many trailing blanks (usually not represented), so it can be represented by a suitable finite prefix.

• "The tape starts with the input (a finite-length word) followed by an infinite amount of blank symbols (often written as #)." Isn't the tape infinitely long on both the left and right though? – user3201708 Apr 27 '18 at 10:24
• @user3201708 It depends on the actual definition, above I assume it's only unbounded on the right. Anyway, the whole argument can be adapted: after finite time, moving one position at a time, writing one cell at a time, the tape will still contain infinitely many blanks on the left and the right. – chi Apr 27 '18 at 10:26
• Sorry to be a pain, but is there any reason you only assumed that the turing machine is unbounded on the right? I can see that the two definitions should have equivilant results, but is having a bounded left standard or something? – user3201708 Apr 27 '18 at 10:30
• @user3201708 Both are somehow standard. Their expressive power is the same: there's no function which can be computed by one the other can not compute. Actually, you'll probably find other equivalent variants when reading about TM theory: multi-tape TMs (e.g. with a read-only input tape, a write-only output tape, and several working tapes) are a common variant, for instance. – chi Apr 27 '18 at 10:37
• Ah, awesome. Thanks for all your help! I wish I could upvote you, but apparently I don't have enough reputation as of yet, hopefully someone else will come along and do the job for me! – user3201708 Apr 27 '18 at 10:40