patternMajor
Why is the blank symbol not considered part of the input alphabet of a Turing machine?
Viewed 0 times
alphabetwhythesymbolpartblankconsideredinputmachineturing
Problem
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?
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#108983, answer score: 25
Revisions (0)
No revisions yet.