1
$\begingroup$

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?

|cite|improve this question
$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – chi Apr 27 '18 at 10:34
  • $\begingroup$ Ah, no problem, I'll quickly fix that up now $\endgroup$ – user3201708 Apr 27 '18 at 10:38
  • $\begingroup$ 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. $\endgroup$ – user3201708 Apr 27 '18 at 10:45
  • $\begingroup$ 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. $\endgroup$ – chi Apr 27 '18 at 10:48
1
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ "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? $\endgroup$ – user3201708 Apr 27 '18 at 10:24
  • $\begingroup$ @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. $\endgroup$ – chi Apr 27 '18 at 10:26
  • $\begingroup$ 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? $\endgroup$ – user3201708 Apr 27 '18 at 10:30
  • $\begingroup$ @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. $\endgroup$ – chi Apr 27 '18 at 10:37
  • $\begingroup$ 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! $\endgroup$ – user3201708 Apr 27 '18 at 10:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.