0
$\begingroup$

I have read that input alphabet of Turing machine is subset of tape symbols because in input alphabet we don't allow blank symbol. But when ever there is a transition to final state the transition as (Blank,Blank,R/L) (First parameter here is input,second is what machine will write on tape,third is direction).It means whenever we have processed input,we will read Blank and replace Blank by Blank and goto final state.But how can blank be written on the tape if it is not part of input alphabet?

With this knowledge I am trying to answer the following statement

"It is decidable that Turing machine will print some non blank character ".

Because Turing machine will always write something on the tape so it should be decidable. But is it possible that there are only two states and there is only one transition as "(Blank,Blank,R/L)"?

$\endgroup$
  • $\begingroup$ "how can blank be written on the tape if it is not part of input alphabet?" -- because we define it like that. $\endgroup$ – Raphael Sep 5 '17 at 5:42
3
$\begingroup$

The formal definition of a turing machine is a 7-tuple $(Q, \Sigma, \Gamma, \delta, q_0, q_{\text{accept}}, q_{\text{reject}})$, where:

  • $Q$ is a finite set of states.
  • $\Sigma$ is a finite set of input symbols (input alphabet).
    • $\Sigma$ does not contain the blank symbol ($\sqcup$).
  • $\Gamma$ is a finite set of tape symbols (tape alphabet).
  • $\sqcup \in \Gamma$ and $ \Sigma \subseteq \Gamma$.
  • $\delta : Q^\prime \times \Gamma \rightarrow Q \times \Gamma \times \{L,R\} $ is the transition function.
    • $Q^\prime = Q - \{q_{\text{accept}}, q_{\text{reject}}\}$
  • $q_0 \in Q$ is the start state.
  • $q_{\text{accept}} \in Q$ is the accept state.
  • $q_{\text{reject}} \in Q$ is the reject state.

The part you want to pay attention to is the definition of the transition function:

$\delta : Q^\prime \times \Gamma \rightarrow Q \times \Gamma \times \{L,R\} $

Note that the transition function accepts inputs that are of the tape alphabet, and writes output that is also of the tape alphabet.


The turing machine is decidable only if it recognizes some language L and and halts for every input.

$\endgroup$
2
$\begingroup$

You asked two questions. The usual rule is to ask one question post, so I will answer the first.

The head can write any symbol in the tape alphabet. It is not restricted to the input alphabet.

The input alphabet is the symbols that can appear in the input (which is initially placed on the tape). That has nothing to do with what the Turing machine can write to the tape during its operation.

$\endgroup$

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.