Theory of Computation · Unit 6 · 10 hrs
Turing Machines
Exam-focused notes for Turing Machines (Theory of Computation, CSC262): what the TU syllabus asks and how it has actually been tested, with 12 solved past questions from this unit.
What this unit covers
- Introduction to Turing Machines (TM)
- Notations of Turing Machine
- Language of a Turing Machine
- Instantaneous Description for Turing Machine
- Acceptance of a string by a Turing Machines
- Turing Machine as a Language Recognizer
- Turing Machine as a Computing Function
- Turing Machine with Storage in its State
- Turing Machine as a enumerator of stings of a language
- Turing Machine as Subroutine
- Turing Machine with Multiple Tracks
- Turing Machine with Multiple Tapes
- Equivalence of Multitape-TM and Multitrack-TM
- Non-Deterministic Turing Machines
- Restricted Turing Machines: With Semi-infinite Tape, Multistack Machines, Counter Machines
- Curch Turing Thesis
- Universal Turing Machine
- Turing Machine and Computers
- Encoding of Turing Machine
- Enumerating Binary Strings
- Codes of Turing Machine
- Universal Turing Machine for encoding of Turing Machine
Encoding of Turing Machine
Define Turing machine as enumerators of strings of a language. Encode the Turing machine TM = ({q0, q1, q2}, {a, b}, {a, b, B}, δ, q2, B, F) with input w = ba and δ is defined as follows: δ(q0, b) → (q1, b, R), δ(q1, a) → (q2, a, R), δ(q2, a) → (q1, a, R), δ(q2, b) → (q2, b, L)[10]
A Turing machine used as an enumerator is a variant of the standard TM equipped with a work tape and a separate output tape (printer). Instead of taking an input and accepting/rejecting it, an enumerator $E$ starts on a blank tape and generates (lists) the ...
Full solved answer →Construct a Turing Machine that accepts the language of odd length strings over alphabet {a, b}. Give the complete encoding for this TM as well as its input string w = abb in binary alphabet that is recognized by Universal Turing Machine.[10]
The TM accepts a string if and only if its length is odd. We use a two-state parity tracking approach: the TM scans the input one symbol at a time, toggling between an "odd count" state and an "even count" state. When it hits a blank (end of input), it acce...
Full solved answer →Acceptance of a string by a Turing Machines
Turing Machine Analysis
Input string: ()))) = ( ) ) ) ) (1 open bracket, 4 close brackets) Transition Table: State ( ) X Y B -------------------------------- $q0$ X, R, $q1$ - - -, -, $q0$ (stay) -, -, $q4$ $q1$ - X, L, $q2$ - Y, L, $q2$ Y, L, $q2$ $q2$ - - X, R, $q0$ Y, R, $q3$ -...
Full solved answer →How does Turing machine accept a string? Design a Turing Machine over the alphabet {0,1,a} that processes the string defined by L = {a01a,a10a,a0101a}. Show both transition diagram and table. Show acceptance of a0101a.[10]
- Alphabet (Σ): $\{0, 1, a\}$ - Language: $L = \{a01a,\ a10a,\ a0101a\}$ (a finite language of exactly 3 strings) - Tape symbols (Γ): $\{0, 1, a, B\}$ where $B$ = blank - Required: definition of acceptance, TM design, transition diagram, transition table, t...
Full solved answer →Turing Machine as a Computing Function
Design a Turing machine that computes a function f(n)=0. [5]
- Function to compute: $f(n) = 0$ for all $n \in \mathbb{N}$. - Input encoding (standard unary): a natural number $n$ is written as $n$ ones, i.e. tape holds $B\,1^n\,B$. - Output encoding: result $0$ is represented by $0$ ones, i.e. a blank tape. - Computa...
Full solved answer →How Turing Machine is used as a computing function? Construct a TM for simulating a function f(x) = 2x for x = {1}. Iterate the TM for input 11 and generate the output 1111.[10]
- Function to compute: $f(x) = 2x$ - Input alphabet symbol: $x \in \{1\}$ (unary representation) - Test input: 11 (i.e., $x = 2$) - Expected output: 1111 (i.e., $f(2) = 4$) - Representation: value $n$ = string of $n$ ones on the tape All data needed to solv...
Full solved answer →Turing Machine as a Language Recognizer
Construct a Turing machine that accepts the language, $L = {a^n b^n \mid n \geq 0}$ [5]
- Language: $L = \{a^n b^n \mid n \geq 0\}$ - Input alphabet: $\Sigma = \{a, b\}$ - Requirement: construct a TM that accepts (halts in accepting state) exactly the strings with equal numbers of as followed by equal numbers of bs, including the empty string ...
Full solved answer →Introduction to Turing Machines
Define Turing machine and its roles. [5]
A Turing Machine (TM) is a theoretical computational model that consists of an infinite tape divided into cells, a read/write head, and a finite control unit. It is formally defined as a 7-tuple: $$TM = (Q, \Sigma, \Gamma, \delta, q0, B, F)$$ Where: Compone...
Full solved answer →Define Turing Machine and explain its different variations. [5]
A Turing Machine (TM) is a theoretical computational model that consists of an infinite tape divided into cells, a read/write head, and a finite control unit. It is formally defined as a 7-tuple: $$TM = (Q, \Sigma, \Gamma, \delta, q0, B, F)$$ Where: Compone...
Full solved answer →Define a Turing machine. Construct a TM that accept $L = { wcw^R \mid w \in {0, 1} \text{ and } c \text{ is } \varepsilon \text{ or } 0 \text{ or } 1 }$. Show that string 0110 is accepted by this TM with sequence of Instantaneous Description (ID). [10]
A Turing Machine (TM) is a theoretical model of computation defined as a 7-tuple: $$TM = (Q, \Sigma, \Gamma, \delta, q0, B, F)$$ Where: Component Meaning -------------------- $Q$ Finite set of states $\Sigma$ Input alphabet (finite set of input symbols) $\G...
Full solved answer →Turing Machine with Multiple Tapes
Describe the Turing machines with multiple tape, multiple track and storage in state. [5]
--- A multiple tape Turing Machine is an extension of the standard TM that has k independent tapes, each with its own read/write head. The standard TM is a special case where k = 1. The transition function is extended as: This means: given the current state...
Full solved answer →Restricted Turing Machines
Describe how multi-stack TM is different from the semi-infinite tape TM? [5]
A Counter Machine is an offline TM whose storage tapes are semi-infinite (the tape extends infinitely in only one direction) and whose tape alphabet contains only two symbols: - Z -- the bottom-of-stack marker, which appears initially on the cell scanned by...
Full solved answer →Make Unit 6 stick
Practice CSC262 with flashcards & quizzes