CS代考计算机代写 algorithm Computational Complexity and Computability

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. qaabbcc
2. xqabbcc
3. xaqbbcc
4. xayqbcc 10. xqaybzc 5. xaybqcc 11. xxqybzc 6. xayqbzc 12. xxyqbzc
13. xxyyqzc 14. xxyyzqc 15. xxyyqzz 16. xxyqyzz 17. xxqyyzz 18. xqxyyzz
19. xxqyyzz
20. xxyqyzz
21. xxyyqzz
22. xxyyzqz
23. xxyyzzq
24. xxyyzqacceptz
qaccept
7. xaqybzc 8. xqaybzc 9. qxaybzc
⊔→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: qw 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”.