Introduction to Turing Machines

Problem 1: What is a turing machine? Break down the formal definition and behaviors of a turing machine, and elaborate on how we can further clarify transitions.

What is a Turing Machine?

• A computational model that is similar to a finite automaton with the exception that...
• It has unrestricted and unlimited memory
• Its storage mechanism is described as a tape that is infinite in both directions
• The input is a finite string that is initially written on the tape
• The machine can move the tape left and right and read/write to the tape
• The turing machines rejecting and accepting states are final; as soon as it enters one of those states, the computation stops immediately (halts)

• A turing machine is a 7-tuple: \( M = (Q, \Sigma, \Gamma, \delta, q_0, q_{accept}, q_{reject}) \) where \(Q, \sum, \Gamma\) are all finite sets, and...
• \(Q\) is a finite set of states
• \(\sum\) is the input alphabet NOT containing the blank symbol \(\sqcup\)
• The blank symbol, \(\sqcup\), is a symbol that is not in \(\sum\) and is used to indicate the end of the input
• \(\Gamma\) is the tape alphabet, where \(\sqcup \in \Gamma\) and \(\sum \subseteq \Gamma\)
• The tape alphabet, \(\Gamma\), includes the blank symbol \(\sqcup\) and the input alphabet \(\sum\)
• \(\delta : Q \times \Gamma \rightarrow Q \times \Gamma \times \{L, R\}\) is the transition function
• \(Q \times \Gamma\): set of all possible configurations of the machine
• \(Q \times \Gamma \times \{L, R\}\): set of all possible actions of the machine where \(L\) is a move to the left and \(R\) is a move to the right
• \(Q \times \Gamma \rightarrow Q \times \Gamma \times \{L, R\}\): The transition function takes a configuration and produces the next configuration depending on where it moves the tape head and what symbol it writes to the tape
• \(q_0 \in Q\) is the start state
• \(q_{accept} \in Q\) is the accept state
• \(q_{reject} \in Q\) is the reject state, where \(q_{reject} \neq q_{accept}\)

• If a turing machine \(M\) tries to move its head to the left off the left-hand end of the tape, the head stays in the same place for that move, despite the transition function indicating \(L\) (left movement)
• The computation of \(M\) continues until it enters an accepting or rejecting state, at which point it halts. If neitehr occurs, \(M\) loops infinitely

• We have established prior that our configuration with tape contents \(uv\) in state \(q\) can be represented as \[ uqv \] where \(u\) is the tape content to the left of the head and \(v\) is the tape content to the right of the head
• We can clarify transitions by letting \(x\) be the last character of the prefix (last symbol to the left of the head)and \(a\) be the first character of the suffix (symbol under the head/currently being read by the machine).
• \(x\) and \(a\) represent specific positions in the configuration. We can then refine the configuration as follows: \[ ux\text{ }q\text{ }av \] where...
• \(u\) is the tape content to the left of the head
• \(x\) is the last symbol to the left of the head
• \(q\) is the current state
• \(a\) is the symbol under the head
• \(v\) is the tape content to the right of the head
• Using this refined configuration format (\(ux \text{ }q \text{ }av\)), we can clarify the transitions as follows where:
(\(ux \text{ }q \text{ }av\)) yields...
• \(u \text{ }r \text{ }xbv\) if \(\delta(q, a) = (r, b, L)\) (result of moving left)
• If the machine is in state \(q\) and reads symbol \(a\) on the tape...
• It changes to new state \(r\)
• It writes symbol \(b\) (replacing \(a\)) on the tape at the current position
• It moves the tape head one position to the left (L)
• The new configuration as of result of the transition is \(u \text{ }r \text{ }xbv\) where...
• The machine is in the new state \(r\)
• the head is positioned over the symbol \(x\) (last symbol to the left of the head)
• The machine is about to read \(x\)
• The symbol \(b\) is to the right of the head (symbol that replaces \(a\))
• \(uxb \text{ }r \text{ }v\) if \(\delta(q, a) = (r, b, R)\) (result of moving right)
• If the machine is in state \(q\) and reads symbol \(a\) on the tape...
• It changes to new state \(r\)
• It writes symbol \(b\) (replacing \(a\)) on the tape at the current position
• It moves the tape head one position to the right (R)
• The new configuration as of result of the transition is \(uxb \text{ }r \text{ }v\) where...
• The machine is in the new state \(r\)
• The head is now positioned over the first symbol of \(v\) (the rest of the tape content to the right of the head)
• The symbol \(b\) is to the left of the head (symbol that replaces \(a\))

• Let's apply these transition rules to the string "nurture" on the tape where our machine results in "NURture" with the head positioned over 'U'
• Initial configuration: \(q_0\text{"nurture"}\) (head at the beginning, in start state \(q_0\))
• Let's say we have the following transitions:
  • \(\delta(q_0, n) = (q_1, N, R)\) - Read 'n', write 'N', move right
  • \(\delta(q_1, u) = (q_2, U, R)\) - Read 'u', write 'U', move right
  • \(\delta(q_2, r) = (q_3, R, L)\) - Read 'r', write 'R', move left
• Step 1: Apply \(\delta(q_0, n) = (q_1, N, R)\)
  • Current configuration: \(q_0nurture\)
  • In our refined transition notation: \(u = \varepsilon\) (empty), \(x = \varepsilon\) (empty), \(q = q_0\), \(a = n\), \(v = urture\) where...
  • \(u\) is the tape content to the left of the head (empty)
  • \(x\) is the last symbol to the left of the head (empty)
  • \(q\) is the current state (start state \(q_0\))
  • \(a\) is the symbol under the head (n)
  • \(v\) is the tape content to the right of the head (urture)
  • Since we're moving right (R), we get: \(uxb \text{ }r \text{ }v \) where...
  • \(u = \varepsilon\) (tape content to the left of the head excluding the last symbol)
  • \(x = \varepsilon\) (last symbol to the left of the head)
  • \(b = N\) (symbol written to the tape)
  • \(r = q_1\) (new state)
  • \(v = urture\) (tape content to the right of the head)
  • The machine is now in state \(q_1\), the head is positioned over 'u', and 'n' has been replaced with 'N'
• Step 2: Apply \(\delta(q_1, u) = (q_2, U, R)\)
  • Current configuration: \(uxb \text{ }r \text{ }v \) = \(N \text{ }q_1 \text{ }urture\)
  • In our refined transition notation: \(u = \varepsilon\), \(x = N\), \(q = q_1\), \(a = u\), \(v = rture\) where...
  • \(u\) is the tape content to the left of the head (empty)
  • \(x = N\) (last symbol to the left of the head)
  • \(q = q_1\) (current state)
  • \(a = u\) (symbol under the head)
  • \(v = rture\) (tape content to the right of the head)
  • Since we're moving right (R), we get: \(uxb \text{ }r \text{ }v \) where...
    • \(u = \varepsilon\) (tape content to the left of the head excluding the last symbol)
    • \(x = N\) (last symbol to the left of the head)
    • \(b = U\) (symbol written to the tape)
    • \(r = q_2\) (new state)
    • \(v = rture\) (tape content to the right of the head)
  • The machine is now in state \(q_2\), the head is positioned over 'r', and 'u' has been replaced with 'U'
• Step 3: Apply \(\delta(q_2, r) = (q_3, R, L)\)
  • Current configuration: \(uxb \text{ }r \text{ }v \) = \(NU \text{ }q_2 \text{ }rture\)
  • In our refined transition notation: \(u = N\), \(x = U\), \(q = q_2\), \(a = r\), \(v = ture\) where...
  • \(u = N\) (content to the left of the head excluding the last symbol)
  • \(x = U\) (last symbol to the left of the head)
  • \(q = q_2\) (current state)
  • \(a = r\) (symbol under the head)
  • \(v = ture\) (tape content to the right of the head)
  • Since we're moving left (L), we get: \(u \text{ }r \text{ }xbv\) where...
  • \(u = N\) (content to the left of the head excluding the last symbol)
  • \(r = q_3\) (new state)
  • \(x = U\) (last symbol to the left of the head)
  • \(b = R\) (symbol written to the tape)
  • \(v = ture\) (tape content to the right of the head)
  • The machine is now in state \(q_3\), the head is positioned over 'U', and 'r' has been replaced with 'R'
• The tape now contains "NURture" with the head positioned over 'U' 【=◈︿◈=】

Problem 2: Define the Language of a Turing Machine and Differentiate between Decidability and Recognizability. What Can be Said about Turing-Recognizable and Turing-Decidable Languages?

Language of a Turing Machine -

• A language \(L\) is the set of all strings that a turing machine \(M\) accepts

• A turing machine decides a language \(L\) if it accepts the strings in it and rejects all the other strings
• In other words, a turing machine decides a language if it correctly accepts or rejects each input
• A language \(L\) is considered turing-decidable if some turing machine decides it
• In other words, a language is turing-decidable if there exists a turing machine that can always halt and give the correct answer (accept or reject) for any input
• Overall:
  • For strings IN the language, the machine must halt and accept
  • For strings NOT in the language, the machine must halt and reject.

• A turing machine recognizes a language \(L\) if it accepts the strings in it and no others
• In other words, a turing machine recognizes a language if it accepts all strings in \(L\) and does not accept any strings not in \(L\) (it may reject them or loop forever)
• A language \(L\) is considered turing-recognizable if some turing machine recognizes it
• In other words, a language is turing-recognizable if there exists a turing machine that halts and accepts all strings in \(L\), and either halts and rejects or loops forever on strings not in \(L\)
• Overall:
  • For strings IN the language, the machine must halt and accept
  • For strings NOT in the language, the machine must NOT accept (it can either reject or loop indefinitely)

• Not All Turing-Recognizable Languages are Turing-Decidable
• This is because a turing machine that recognizes a language may not always halt on strings not in the language (given that it can loop indefinitely)
• All Turing-Decidable Languages are Turing-Recognizable
• This is because a turing machine that decides a language must also recognize it (given that it halts on all inputs)

Problem 3: Define the following Turing Machine Variants: Enumerator, Multitape TM, and NDTM

Enumerator -

• What: A turing machine that enumerates (lists) all strings in a language
• In other words, an enumerator generates all strings in a language one by one
• How to construct an enumerator:
• Given a language \(L\), we can construct an enumerator that generates all strings in \(L\) one by one
• The enumerator works by:
• Enumerating all possible strings in lexicographic (dictionary) order
• For each string, checking if it is in the language \(L\)
• If it is, the enumerator halts and accepts the string
• If it is not, the enumerator continues to the next string
• The enumerator halts when all strings in \(L\) have been generated and checked

• What: A turing machine with multiple finite number of tapes, each with its own read-write head where...
• the input appears on tape 1, and the other tapes are initially blank
• On each transition, we read all the tapes at once
• On each transition, we write to all the tapes at once
• On each transition, we move left or right on all the tapes at once
• \(\delta: Q \times \Gamma^k \rightarrow Q \times \Gamma^k \times \{L, R\}^k\) where...
• \(Q\): set of states
• \(\Gamma\): tape alphabet
• \(k\): number of tapes
• \(\{L, R\}^k\): set of possible moves for each tape head (left or right)
• We use # as a tape separator symbol
• We use ȧ (symbol (a, b, c, etc) with a dot above it) to indicate the movement of the head

• What: A turing machine that can make multiple transitions from a single configuration where...
• \(\delta: Q \times \Gamma \rightarrow P(Q \times \Gamma \times \{L, R\})\)
• \(Q\): set of states
• \(\Gamma\): tape alphabet
• \(P(Q \times \Gamma \times \{L, R\})\): power set of \(Q \times \Gamma \times \{L, R\}\) (set of all possible transitions)
• We visit the tree using breadth-first search (level by level) as opposed to depth-first search (following paths to their ends)
• This means that we explore all possible configurations at the current computation step before moving to the next step to avoid spinning indefinitely

Problem 4: Break down each component of the church-turing thesis? What does the thesis state?

Formal Description (component 1) -

• The 7-tuple definition of a turing machine

• Configuration Rules and Types + transition clarifications

• Descriptions of algorithms are equivalent in power to turing machines
• In other words, any algorithm can be computed by a turing machine
• An algorithm is any clear, unambiguous, and finite set of instructions to a computer, each step of which performs only a finite amount of work
• It defines the entire way we think about algorithms
• Why: turing machines provide formal instructions on how we define algorithms

• The Church-Turing Thesis tells us that the formal definition, quasi-formal definition, and algorithmic high-level description of algorithms are equivalent in power
• In other words, we can use any of the three components to describe a solution to a computational problem, and they all have the same expressive power as a Turing machine

Problem 5: Define how a TM \(M\) decides the following language: \[ A = \{\langle G \rangle \mid G \text{ is a connected undirected graph}\} \]
Step 0: Understand the Language (Prerequisite/for your understanding)

• Input: \(\langle G \rangle\): the encoding of \(G\)
• Condition: \(G\) is a connected undirected graph
• If \(G\) is represented as the following graph:

• Then \(\langle G \rangle\) would be the set of vertices and edges of the graph
• In this case, \(\langle G \rangle = \{(1, 2, 3, 4), (1, 2), (2, 3), (3, 1), (1, 4)\}\)

• The TM \(M\) will scan the tape to ensure there are two lists and that they are in proper form
• The first list will contain a list of distinct decimal numbers (the node list; representing the vertices of the graph)
• It is said to be in proper form if it contains no duplicate numbers
• The second list will contain a list of pairs of decimal numbers (the edge list; representing the edges of the graph)
• It is said to be in proper form if every node in the edge list also appears in the node list.
• To verify the encoding for the first list, the TM will do the following:
• Check if the first list is in proper form (comma separated, no duplicates)
• Check that the list is properly terminated
• If conditions arent met, the TM will reject the input
• To verify the encoding of the second list, the TM will do the following:
• Check if the second list is in proper form (each pair is comma separated, no duplicates)
• Check that every node in the edge list also appears in the node list
• If conditions arent met, the TM will reject the input

• The TM will mark the first node (1) with a dot on the leftmost digit as follows:

• The TM will scan the list of nodes to find an undotted node (2) = \(n_{1}\) and flag it by underlining it
• TM will scan the list again until it finds a dotted node (1) = \(n_{2}\) and then underlines it (1 is now dotted and underlined)
• TM will then scan list of edges. For each edge, TM will test whether the two underlined nodes (\(n_{1}\) and \(n_{2}\)) are are the ones appearing in that edge
• If they are: move onto stage 3 where...
  • TM dots \(n_{1}\), removes its underline, and then goes to the first step of stage 2 with \(n_{2}\) as the new \(n_{1}\) (\(n_{1} = 2\))
  • This will continue until all nodes are dotted
• If they are not: TM checks next edge on the list, if there are no more edges, then \(\{n_{1}, n_{2}\}\) is not an edge of \(G\)

• TM will scan list of nodes to determine if they are all dotted...
• If they are: TM enters the accept state and halts
• If they are not: TM enters the reject state and halts