COS151
Tutorial 5
Topics Covered
• Cantor's Diagonalisation Proof which demonstrates the existence of over-countably
infinitely many functions.
• Existence of the Universal Turing Machine (UTM)
• Fundamental Theorem: The halting problem is un-decidable
Cantor's Diagonalisation Proof which demonstrates the
existence of over-countably infinitely many functions.
• To better understand this proof, we will try to answer the questions
below.
• What does countably infinite and over – countably infinite mean?
• Are even numbers countably infinite or over- countably infinite?
• Is this set countably infinite { ……,-2, 1, 0, 1, 2,….} ?
• Finally, we answer why functions are over – countably infinite and why
Turing machines are countably infinite.
Countably infinite and over – Countably infinite
• A set is countably infinite if its elements can be put into a one-to-one
correspondence with the natural numbers (N={1,2,3,4,… })
• Let us explain this using prime numbers. Are even numbers countably infinite?
prime numbers Natural numbers
this means 1st prime number = 2(its natural
number).
2 1 Correspondence function is f(n) = 2n
4 2
6 3
8 4 First even number is f1 = 2(1)
Second even number f2 = 2(2)
Third is f3=2(3)
one on one correspondence And so on to infinity
Questions
• Are prime numbers countably infinite ? Why ?
• Is this set countably infinite { ……,-2, 1, 0, 1, 2,….} ? Why?
Why Turing machines are countably infinite.
• A Turing machine is defined by:
• A finite set of states
• A finite alphabet of symbols
• A transition function (rules for moving on the tape)
• Turing machine is just a finite description (a string of symbols), we can encode
(represent) each machine as a finite sequence of symbols.
• Since all possible symbol form a countable set, the set of all possible Turing
machines is countably infinite because we can arrange the symbols in a sequence
Why functions are over – countably infinite
I NEED A PAPER AND A MARKER
The Universal Turing Machine
• “A Universal Turing Machine can be defined as a theoretical construction that can
simulate the behaviour of other machines. This is done specifically by reading, apart
from the input tape it simulates, a description of how this very machine it is simulating
would work, and transition rules showing how it would respond to the input. This gives
the UTM the character of a general-purpose computational device that can execute
any arbitrary computable function.”
Theorem
• There exists is a Turing machine that can compute whatever is computable by another
Turing machine.
Proof by Construction- Additional Literature
• The UTM uses three tapes, each with a distinct purpose:
• 1. Input Tape:
• This tape contains the input word consisting of:
• The description of a Turing Machine 𝑇 (i.e., ⟨𝑇⟩).
• The actual input 𝑤 for 𝑇.
• 𝑈 reads this tape to extract the rules of 𝑇 and simulate its execution
• 2. Work Tape:
• This tape starts empty and is used by 𝑈 to perform computations, just as 𝑇 would have used its own
tape.
• The work tape mimics the tape of 𝑇, meaning all computations and modifications that 𝑇 would
perform on its own tape, 𝑈 performs here.
• 3. Auxiliary Tape
• This tape is also empty initially.
• It is used to store the current state of the simulated machine 𝑇.
• 𝑈 tracks the execution of 𝑇 by recording its state and comparing it with 𝑇’s final states to determine if
it should halt.
The Turing machine T’s description
The notation
• T=(Q,Σ,Γ,δ,q1,⊔,F) represents the formal definition of a Turing Machine (TM) T. Let’s break it down:
1. Q – The finite set of states.
1. This includes all possible states the Turing machine can be in.
2. Σ – The input alphabet.
1. This is the set of symbols that the input string can be composed of.
2. It does not include the blank symbol ⊔.
3. Γ – The tape alphabet.
1. This is the set of symbols that can be written on the tape.
2. It includes Σ and also additional symbols such as the blank symbol ⊔.
4. δ – The transition function.
1. This function describes how the machine moves and changes state.
2. It is defined as: δ:Q×Γ→Q×Γ×{L,R}
3. Given a current state and a tape symbol, it determines:
1. The next state.
2. The symbol to write.
3. The direction to move the tape head (Left LLL or Right RRR).
Cont.
1.q1 – The start state.
1. The initial state of the Turing machine where
computation begins.
2.⊔ – The blank symbol.
1. A special symbol used to represent empty tape cells.
3.F – The set of final (accepting) states.
1. If the machine reaches one of these states, it halts
and accepts the input.
The Algorithm the Turing Machine U executes
to simulate T
Test your understanding
A Universal Turing Machine 𝑈 is given an input that consists of:
1. The encoded description ⟨𝑇⟩ of a Turing Machine 𝑇, which has the following transition
rules:
• 𝛿(𝑞1,0)=(𝑞2,1,𝑅)
• 𝛿(𝑞2,1)=(𝑞3,0,𝐿)
• 𝛿(𝑞3,1)=(𝑞accept,1,𝑅)
2. The input string 01, placed on the input tape.
Using the algorithm for 𝑈, simulate the first three steps of execution.
• What does 𝑈 do in each step?
• What will be the contents of the work tape after three transitions?
• Will 𝑇 reach an accepting state? If so, at which step?
The Halting Problem – Textbook Chapter 17
Definition:
• “In computability theory, the halting problem is the problem of determining, from a description of an
arbitrary computer program and an input, whether the program will finish running, or continue to run
forever. The halting problem is undecidable, meaning that no general algorithm exists that solves the
halting problem for all possible program–input pairs.”
Core Question:
• Can we create an algorithm that determines whether any given program will halt for a specific input?
Answer:
• No, it is impossible to design a generalised algorithm that can accurately determine whether any arbitrary
program will halt. The only way to know if a specific program halts is to run it and observe the outcome.
This makes the Halting Problem an undecidable problem.
Core Point
• The halting problem is not solvable
Proof- By Contradiction
• Use your knowledge from WTW115 to make sense of this
Test your understanding
• In the proof, the program Strange is constructed. Explain how Strange leads to a
contradiction.
• Why does running Strange with itself as input create a contradiction?
• How does the Halting Problem relate to Turing Machines? Can a Turing Machine
decide whether an arbitrary program halts?
