## Description

1. [6 marks] This question asks you to examine the formal definitions of a TM and related concepts closely. Based

on these definitions, answer the following.

(a) A configuration of a Turing Machine (TM) consists of three things. What are these three things?

(b) Can a Turing machine ever write the blank symbol t on its tape?

(c) Can the tape alphabet Γ be the same as the input alphabet Σ?

(d) Can a Turing machine’s head ever be in the same location in two successive steps?

(e) Can a TM contain just a single state?

(f) What is the difference between a decidable language and a Turing-recognizable language?

2. [8 marks] This question gets you to practice describing TM’s at a semi-low level. Give an implementation-level

description of a TM that decides the language

L = {x | x contains twice as many 0s as 1s}.

By implementation-level description, we mean a description similar to Example 3.11 in the text (i.e. describe

how the machine’s head would move around, whether the head might mark certain tape cells, etc. . . . Please do

not draw a full state diagram (for your sake and for ours)).

3. [9 marks] This question investigates a variant of our standard TM model from class. Our standard model

included a tape which was infinite in one direction only. Consider now a TM whose tape is infinite in both

directions (i.e. you can move left or right infinitely many spaces on the tape). We call this a TM with doubly

infinite tape.

(a) [3 marks] Show that a TM with doubly infinite tape can simulate a standard TM.

(b) [5 marks] Show that a standard TM can simulate a TM with doubly infinite tape.

(c) [1 mark] What does this imply about the sets of languages recognized by both models?

4. [10 marks] This question studies closure properties of the decidable and Turing-recognizable languages.

(a) [5 marks] Show that the set of decidable languages is closed under concatenation.

(b) [5 marks] Show that the set of Turing-recognizable languages is closed under concatenation. (Hint: This

is trickier than part (a) because if a (deterministic) Turing machine decides to split an input string x as

x = yz and check if y ∈ L1 and z ∈ L2, i.e. to check if x ∈ L1 ◦ L2, then running the recognizer for L1

on y (say) may result in an infinite loop if y 6∈ L1.)

1

5. [5 marks] This question allows you to explore variants of the computational models we’ve defined in class.

Let a k-PDA be a pushdown automaton that has k stacks. In this sense, a 0-PDA is an NFA and a 1-PDA

is a conventional PDA. We know that 1-PDAs are more powerful (recognize a larger class of languages) than

0-PDAs. Show that 2-PDAs are more powerful than 1-PDAs. (Hint: Recall from A4 that the language L =

{a

nb

nc

n | n ≥ 0} is not context-free.)

2