Computational Complexity and Computability
Lecture 3 – Algorithms & Computable Functions
Koushik Pal
University of Toronto
January 18, 2021
Example 1 – PAL
Goal: Describe a TM on the alphabet {, } for the languauge
PAL = {set of even length palindromes} = {yyreverse | y ∈ {,}∗}. Solution.
, → R
q
⊔→L
⊔ → R
q
q
q , → L
q ⊔→L q
qaccept
, → R
→ ⊔, R
→ ⊔, L
→ ⊔, R
→ ⊔, L
⊔→R
Execution on input , → R
q
⊔→L
q
q ⊔→R q
, → L
1. q
2. q
3. q
4. q
5. q
6. q
7. q 8. q 9. q
10. q 11. q 12. q
13. q ⊔ 14. q 15. q
16. q
17. q 18. q
19. 20. 21. 22. 23. 24.
q q q q⊔ q q
25. q 26. q 27. q
28. q
29. qaccept
qaccept
q ⊔→L q
, → R
→ ⊔, R
→ ⊔, L
→ ⊔, R
→ ⊔, L
⊔→R
Example 2
Goal : Describe a TM on the alphabet {a, b, c} for the languauge L={anbncn |n∈N}.
Solution.
Σ = {a,b,c}, Γ = {a,b,c,x,y,z,⊔}
y, z → R q
a → x, R
a, y → R
q
b → y, R
x→R
b, z → R
q
c → z, L
a, y, b, z → L
q
qaccept
⊔→L
Execution on input aabbcc
a,y→R b,z → R
a,y,b,z → L
c → z, L
y, z → R q
a→x,R
b → y, R
q q
x→R
q
1. qaabbcc
2. xqabbcc
3. xaqbbcc
4. xayqbcc 10. xqaybzc 5. xaybqcc 11. xxqybzc 6. xayqbzc 12. xxyqbzc
13. xxyyqzc 14. xxyyzqc 15. xxyyqzz 16. xxyqyzz 17. xxqyyzz 18. xqxyyzz
19. xxqyyzz
20. xxyqyzz
21. xxyyqzz
22. xxyyzqz
23. xxyyzzq
24. xxyyzqacceptz
qaccept
7. xaqybzc 8. xqaybzc 9. qxaybzc
⊔→L
Computable Functions
Definition
A function f : A → B is computable if there is a TM M such that for all input w ∈ A, the machine halts with only f(w) ∈ B on the tape and the head pointing to the beginning of the output.
In other words,
Initial Configuration: qw Final Configuration: qacceptf(w)
⊔
w
⊔
⊔
f(w)
⊔
… …
… …
q qaccept
Example
Goal: Show that the function f (x, y) = x + y is computable.
Integer Domain
Decimal, e.g., Binary, e.g., Unary, e.g.,
For this problem, we will take the input in unary. The input alphabet is Σ = {, $}, and the input is represented as x$y.
Example
Goal: Show that the function f (x, y) = x + y is computable. Solution.
→R →R
→L
q
q
$ → , R
q
⊔ → L
q
→ ⊔, L
⊔ → R
qaccept
Execution on input $ →R →R
→L
⊔→R
q qaccept
$ → , R
q
1. q $
2. q $
3. q $
4. q $
5. q $
6. q $
7. q
8. q
q
9. 10. 11. 12. 13. 14. 15. 16.
⊔→L →⊔,L q
q q q q q q q q
17. q
18. q
19. q
20. q
21. q
22. q ⊔ 23. qaccept
Church-Turing Thesis
Turing’s Thesis
Any computation carried out by mechanical means can be performed by a Turing Machine.
Definition
An algorithm for a function f(w) is a Turing Machine that computes f(w).
Note: When we say “There is an algorithm”, what we mean is “There exists a Turing Machine that executes the algorithm”.