0
$\begingroup$

For Turing machines, if the input variables increase, will the state set Q increase ? will the tape alphabet Γ increase?

For example, for the SAT problem, the first question is whether the Boolean expression of one variable is satisfied, the second is whether the Boolean expression of three variables is satisfied. Does the latter need a larger state set Q and a larger tape alphabet Γ than the former?

The book Introduction to the Theory of Computation that I've been using for reference define a Turing machine as follows:

A Turing machine is a 7-tuple, (Q,Σ,Γ,δ,q_0 ,q_accept ,q_reject ), where Q, Σ, Γ are all finite sets and

  1. Q is the set of states,
  2. Σ is the input alphabet not containing the blank symbol,
  3. Γ is the tape alphabet, where ☐ ∈ Γ and Σ ⊆ Γ,
  4. δ: Q × Γ→Q × Γ × {L,R} is the transition function,
  5. q_0 ∈ Q is the start state,
  6. q_accept ∈ Q is the accept state, and
  7. q_reject ∈ Q is the reject state, where q_reject ≠ q_accept .
Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

A Turing machine is fixed in size. Just as a piece of code doesn't increase in size when given bigger inputs, also a TM doesn't.

The $TM$ has to be defined beforehand, and its description should not depend on the particular specific input that was given to it.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Thank you very much for your answer. I would like to make it more specific that if the input variables increase, will the state set change or remain unchanged? How does the tape alphabet change? Will it increase? $\endgroup$
    – lz9866
    Oct 2, 2021 at 2:51
  • $\begingroup$ As I said, the description of Turing machines (their states, transitions, alphabet, etc.) does not depend on the input. Hence the alphabet size will not increase, nor the states will change $\endgroup$
    – nir shahar
    Oct 2, 2021 at 8:40
  • $\begingroup$ @lz9866 The input is the thing on the tape. The machine itself doesn't change. $\endgroup$
    – GManNickG
    Oct 7, 2021 at 2:13
  • $\begingroup$ Thank nir shahar and GManNickG for your answers. I approve that the state set will not change. But I think that tape alphabet will change. Refer to the book Introduction to the Theory of Computation，the transition function is δ: Q × Γ→Q × Γ × {L,R} , which means that every time the TM reads a variable or other auxiliary symbols, it transfer the state once. In that way, if the input variables increase, the tape alphabet will increase. Is there anything wrong with my discussion here？ $\endgroup$
    – lz9866
    Oct 14, 2021 at 8:01
  • $\begingroup$ The alphabet is the set of all "allowed" letters. Hence, it must be fixed and will not change. I think you are confused with the following: the particular sbol a TM will use does depend on the input. The distinction is that the TM is allowed to choose a differet letter from the fixed alphabet, but isn't allowed to change that fixed alphabet. $\endgroup$
    – nir shahar
    Oct 14, 2021 at 15:39

Your Answer

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

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