15
$\begingroup$

Definitions of Turing machines are always explicit about the blank symbol not being part of the input alphabet.

I wonder what goes wrong when you would make it part of the input alphabet, because effectively the blank symbol already seems to be part of the input.

To explain that 'seems' in the last sentence, consider the following.

In the default setup, an infinite number of blank symbols appear on the right of the input. When the tape head moves over the first blank symbol, computation can just continue, as it doesn't need to be an accept or reject state.

Now suppose the computation would subsequently write symbols from the input alphabet to the right of that first blank symbol, then return to the leftmost position while also returning to the start state. It would then 'start over' with a different tape. Effectively, it now starts with a different input, where there are input symbols to the right of the blank that weren't there before. The input seems to effectively include the blank symbol. The further behavior of the machine could now also be different: after encountering the blank again, it will now encounter different symbols to the right.

Supposing this scenario is indeed possible, why wouldn't you consider the blank symbol part of the input alphabet and why wouldn't you allow including it as part of the 'initial' input?

Perhaps it is just a way to define the input such that it isn't always infinite?

Improve this question
$\endgroup$
0

3 Answers 3

Reset to default
25
$\begingroup$

The main reason is that it allows the machine to detect the end of its input: it's (the character before) the first blank. If you allowed blanks in the input, the machine could never know whether it might find more input by scanning farther to the right. Of course, you could solve that by having a special "end of input" character but then you have to insist that that can't appear in the input, so you've just shifted the problem one level deeper.

It also makes the initial conditions much easier to specify: the input is the non-blank section of the initial tape, which must be finite and contiguous. And if you want a blank character to be a part of the input alphabet, you can always add an extra character (call it "space" or something) and have the machine behave however you want when it sees it.

Improve this answer
$\endgroup$
5
  • 2
    $\begingroup$ Ah, of course, without being able to determine the end of the initial input, some calculations would be impossible. But otherwise there is nothing special about the symbol. And I guess it's matter of terminological economy to use the blank symbol, as you need that one in your alphabet anyway. I think it would've been more obvious to me when initially defined with an explicit end-of-input symbol and a remark it wasn't strictly necessary and often left out. $\endgroup$
    – Confusion
    Commented May 5, 2019 at 13:46
  • 1
    $\begingroup$ There are simple input encodings that don't require an extra symbol. For example, one can simulate a four character alphabet by considering pairs of characters 00, 01, 10, and 11, and then (for example) designate a decoding $\{00\} \rightarrow 0, \{11\} \rightarrow 1, \{10, 01\} \rightarrow b$. But it greatly simplifies matters to allow a third character, and doing so produces no real downsides. $\endgroup$
    – Yonatan N
    Commented May 6, 2019 at 7:53
  • 2
    $\begingroup$ Seeing as the Turing machine needs rules that govern what it does if it reads a blank, and it may have a rule that tells it to write a blank, doesn't that mean that the blank is indeed part of its alphabet? I don't see why the input may not contain blanks. How about encoding input-items using the non-blank characters, and a single blank as a separator? Then multiple consecutive blanks indicate the end of the input. $\endgroup$
    – Rosie F
    Commented May 6, 2019 at 10:47
  • 3
    $\begingroup$ @YonatanN Sure. That's "simple" but having a blank symbol is simpler. $\endgroup$
    – David Richerby
    Commented May 6, 2019 at 12:26
  • 4
    $\begingroup$ @RosieF The blank is part of the tape alphabet; the input alphabet is a subset of that. And, sure, you could set up conventions for how the input can contain blanks under certain circumstances (as you did) but that just makes the definitions more complex. More complex definitions mean that it's harder to prove things about Turing machines. And, since Turing machines are really only used for proving things (if you want to design an actual computer, it's not going to be a TM) that's not a good trade-off. $\endgroup$
    – David Richerby
    Commented May 6, 2019 at 12:40
6
$\begingroup$

You can define the blank symbol to be part of the alphabet. The problem with that is that if a Turing machine with input b010010b (where b stands for blank) never reads past the second b, then the machine will behave exactly the same way on all inputs starting with b010010b.

These Turing machines are called prefix Turing machines, and they are very useful for proving some theorems about Kolmogorov complexity.

Improve this answer
$\endgroup$
6
$\begingroup$

Very short answer: the tape alphabet is the set of symbols that can appear on the tape, and it includes the blank symbol. The input alphabet is the set of symbols that can appear in the initial input, and it does not include the blank symbol. The main alphabet the machine cares about is the tape alphabet: it still needs rules for what to do when it sees a blank, for example.

This distinction is important, as others have said, so that the machine can tell where its input ends. It's the same reason you can't (usefully) put a zero-character in the middle of a string in C: the zero-character is reserved to mean "the last non-zero character before this is the end of the data, so when you see this, you're done". If you need to expect zero-characters in the middle of the string, writing strlen gets a whole lot harder.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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