Week 10 - Decidability / undecidability and more

Question 1

Decidable
sirs definition

Answer 1

. Terminates
. sound -> if M(w) = 1 then w exists in Language
.complete if w exists in language M(w) = 1 [turing machine accepts the string]

Question 2

“If a language L is decidable, what can we say about its complement L̄? Explain the proof concept.”

Answer 2

“If L is decidable, then L̄ is also decidable. Here’s why:

Since L is decidable, there exists a TM M that decides it
To decide L̄, we can build a new TM M’ that:

Uses M as a subroutine
Runs M on input w
Reverses M’s answer (accepts when M rejects, rejects when M accepts)

M’ will always halt (since M does)
M’ will correctly decide L̄ by definition

This shows decidable languages are closed under complement.”

Question 3

decidable expanded

Answer 3

. halts
. correctly accepts all strings in L
. correctly rejects all strings in L

Question 4

undecidable

Answer 4

No turing machine exists that satisfies all properties found in decidability:

. halts AND correctly accepts all strings in L AND correctly rejects all strings in L

Question 5

What is the input to a Universal Turing Machine

Answer 5

encoding of the turing machine and the input word

Question 6

What is the purpose of a Universal Turing Machine (

Answer 6

A Universal Turing Machine simulates the operation of another Turing machine M on input

Accepts ⟨code(𝑀), 𝑤⟩ if M accepts 𝑤

Rejects ⟨code(𝑀) , 𝑤⟩ if M rejects 𝑤

Gets stuck if 𝑀 does not halt on 𝑤

Question 7

How are Turing machines encoded for input to a UTM?

Answer 7

code(𝑀) = ⟨ 𝑞init , 𝑞accept, 𝑞reject ,⟨𝛿⟩⟩

where
𝛿
δ is the transition function of
𝑀
M.

Example :

Suppose
𝑀
M is a Turing machine with:

𝑞init = 𝑞0

𝑞accept =𝑞𝑎

𝑞reject = 𝑞𝑟

δ:
𝛿(𝑞0,0) = (𝑞1 ,1,𝑅)

𝛿(𝑞1 ,1) = (𝑞𝑎,1,𝐿)

The encoding code (𝑀)
code(M) would look like:

code (𝑀) = ⟨𝑞0 , 𝑞𝑎 , 𝑞𝑟 , ⟨(𝑞0, 0, 𝑞1 ,1 , 𝑅) , (𝑞1 , 1 , 𝑞𝑎,1,𝐿)⟩⟩

This string representation can now be processed by a Universal Turing Machine to simulate the behavior of
𝑀
M.

Question 8

can a universal turing machine decide an undecidable language

Answer 8

Can a Universal Turing Machine Decide a Language L?

Decidable Languages:

If a language L is decidable, there exists a Turing machine M that always halts and gives correct answers.

A Universal Turing Machine (UTM) simulates M and will also halt and decide L.

Undecidable Languages:

If a language L is undecidable, no Turing machine M can always halt and decide it.
A UTM, simulating M, will behave the same (e.g., loop indefinitely) and cannot decide L.
Conclusion:
A UTM can decide L if L is decidable but cannot decide L if L is undecidable.