Notes - Models of Computation MT23, Turing machines

Created: November 10, 2023

Flashcards

Describe what a Turing machine does at each step in its computation, as a sequence of 4 things.
  • Read the symbol under its head
  • Write a new symbol
  • Move its head left or right
  • Enter a new state

Suppose $w = w _ 1 \cdots w _ n$ is the input string to a Turing machine. What are the initial tape contents?
\[\vdash w_1 w_2 \cdots w_n \sqcup \sqcup \cdots\]

where $\vdash \in \Gamma$ is the right endmarker, and $\sqcup \in \Gamma$ is the blank symbol.

Can you give the formal definition of the components a one-tape deterministic Turing machine?

A 9-tuple

\[(Q, \Sigma, \Gamma, \vdash, \sqcup, \delta, q_0, q_\text{acc}, q_\text{rej})\]

where

  • $Q$ finite set, states
  • $\Sigma \subseteq \Gamma$ finite set, input alphabet
  • $\Gamma$ finite set, tape alphabet
  • $\vdash \, \in \Gamma \setminus \Sigma$, left endmarker
  • $\sqcup \in \Gamma \setminus \Sigma$, blank symbol
  • $\delta : Q \times \Gamma \to Q \times \Gamma \times \{L, R\}$, transition function
  • $q _ 0, q _ \text{acc}, q _ \text{rej} \in Q$, start, accept and reject states with $q _ \text{acc} \ne q _ \text{rej}$

A one-tape deterministic Turing machine is defined by a 9-tuple

\[(Q, \Sigma, \Gamma, \vdash, \sqcup, \delta, q_0, q_\text{acc}, q_\text{rej})\]

where

  • $Q$ finite set, states
  • $\Sigma \subseteq \Gamma$ finite set, input alphabet
  • $\Gamma$ finite set, tape alphabet
  • $\vdash \, \in \Gamma \setminus \Sigma$, left endmarker
  • $\sqcup \in \Gamma \setminus \Sigma$, blank symbol
  • $\delta : Q \times \Gamma \to Q \times \Gamma \times \{L, R\}$, transition function
  • $q _ 0, q _ \text{acc}, q _ \text{rej} \in Q$, start, accept and reject states with $q _ \text{acc} \ne q _ \text{rej}$

Can you give the intuitive meaning of $\delta(q, a) = (q’, b, L)$?

When in state $q$ scanning symbol $a$:

  • Enter state $q’$
  • Write $b$ over tape cell
  • Move the head left by one cell

A one-tape deterministic Turing machine is defined by a 9-tuple

\[(Q, \Sigma, \Gamma, \vdash, \sqcup, \delta, q_0, q_\text{acc}, q_\text{rej})\]

where

  • $Q$ finite set, states
  • $\Sigma \subseteq \Gamma$ finite set, input alphabet
  • $\Gamma$ finite set, tape alphabet
  • $\vdash \, \in \Gamma \setminus \Sigma$, left endmarker
  • $\sqcup \in \Gamma \setminus \Sigma$, blank symbol
  • $\delta : Q \times \Gamma \to Q \times \Gamma \times \{L, R\}$, transition function
  • $q _ 0, q _ \text{acc}, q _ \text{rej} \in Q$, start, accept and reject states with $q _ \text{acc} \ne q _ \text{rej}$

However, this definition is missing three additional restrictions. What are they?
  • The left endmarker is never overwritten
  • The machine never moves left of the endmarker
  • Once the machine enters $q _ \text{acc}$ or $q _ \text{rej}$, it never leaves it

A one-tape deterministic Turing machine is defined by a 9-tuple

\[(Q, \Sigma, \Gamma, \vdash, \sqcup, \delta, q_0, q_\text{acc}, q_\text{rej})\]

where

  • $Q$ finite set, states
  • $\Sigma \subseteq \Gamma$ finite set, input alphabet
  • $\Gamma$ finite set, tape alphabet
  • $\vdash \, \in \Gamma \setminus \Sigma$, left endmarker
  • $\sqcup \in \Gamma \setminus \Sigma$, blank symbol
  • $\delta : Q \times \Gamma \to Q \times \Gamma \times \{L, R\}$, transition function
  • $q _ 0, q _ \text{acc}, q _ \text{rej} \in Q$, start, accept and reject states with $q _ \text{acc} \ne q _ \text{rej}$
  • (and also the additional restrictions that if the read head never moves left of the left endmarker, once the machine enters the accept state or the reject state, it never leaves it)

Can you:

  • Define what is meant by a configuration of a TM
  • Describe the next-configuration relation
  • Describe the language recognised by a Turing machine

A configuration $(u, q, v)$ of a Turing machine is an element of $\Gamma^\star \times Q \times \Gamma^\star$ representing:

  • The current state is $q$
  • The current tape contents are $uv$
  • The position of the read head is over the first symbol of $v$

The next configuration relation is defined by

  • If $\delta(q, b) = (q’, c, L)$, then $(ua, q, bv) \to (u, q’, acv)$
  • If $\delta(q, b) = (q’, c, R)$, then $(ua, q, bv) \to (uac, q’, v)$

Also, if the tape head is at the very end of the tape’s contents, i.e. in $(ua, q, \epsilon$), this is interpreted as equivalent to $(ua, q, \sqcup)$.

(with special cases for head being to the right of a configuration).

Let $\to^\star$ be the reflexive and transitive closure of $\to$.

The language recognised by a TM is the set of strings $w$ such that $\exists C$ where $C$ is a configuration with state $q _ \text{acc}$ and

\[(\epsilon, q_0, {\vdash w}) \to^\star C\]

What does it mean for a language to be recursively enumerable?

It is recognised by some Turing machine.

What are the languages recognised by a Turing machine called?

Recursively enumerable.

What are the three possible outcomes for a run of a Turing machine, and what does it mean to halt?
  • Accept
  • Reject
  • Loop

Halts if it accepts or rejects.

What is the initial tape setup when you have a $k$-tape deterministic Turing machine?

The first tape contains the input word, all the others are blank.

In terms of the states $Q$, the tape alphabet $\Gamma$ and $\{L, R\}$, what does the transition function for a $k$-tape deterministic Turing machine look like?
\[\delta : Q \times \Gamma^k \to Q \times \Gamma^k \times \\{L, R\\}^k\]

In terms of the states $Q$, the tape alphabet $\Gamma$ and $\{L, R\}$, what does the transition function $\delta$ for a one-tape non-deterministic Turing machine look like?
\[\delta : Q \times \Gamma \to \mathcal P(Q \times \Gamma \times \\{L, R\\})\]

Can you characterise the behaviour of a universal Turing machine $U$?

For any TM $M$ and any input $x$ of $M$, $U$ accepts $\langle M, x\rangle$ if and only if $M$ accepts, and $U$ halts if and only if $M$ halts.



Related posts