J003 - Fundamental Concepts of Computer Science
Prof. Juraj Hromkoviˇc
Exercise sheet 1
deadline: 29.5.2015
Common definitions
Σbool = {0, 1}
LU = {Kod(M)#w | w ∈ Σ∗
bool and M accepts w}
LH = {Kod(M)#w | w ∈ Σ∗
bool and M halts on w}
A function t : N → N is called time constructible, if there exists an MTM (multi-tape Turing
machine) A, such that
(i) TimeA ∈ O(t(n))
(ii) for any input 0n
, n ∈ N, A generates the word 0t(n)
on the first working tape and halts
in qaccept.
Exercise 1.
Prove that LH ≤R LU .
Exercise 2.
Describe how to find, for any infinite language L ⊆ {0, 1}∗
, a subset of L that is not
recursively enumerable. Justify your claim.
Exercise 3.
Consider the languages
LH,001 = {Kod(M) | M halts on 001} and
LEQ = {Kod(M)#Kod(M ) | L(M) = L(M )}
Prove the following claims:
(a) LH,001 ≤R LU
(b) LU ≤R LEQ
1
Exercise 4.
Let wi be the i-th word over Σbool in canonical order and let Mi be the i-th Turing machine
in canonical order. We consider two languages
(a) L1 = {w ∈ Σ∗
bool | w = w5i+3 for some i ∈ N and Mi does not accept w5i+3} and
(b) L2 = {w ∈ Σ∗
bool | w = wi for some i ∈ N and M5i+3 does not accept wi}
Prove, analogously to the proof for the diagonal language, that one of the two languages is
not recursive and argue why such a proof is not possible for the other language.
Exercise 5.
We consider the language
Lall = {Kod(M) | L(M) = Σ∗
bool}
Prove that Lall ∈ LR.
Exercise 6.
Consider the language
Ldisjoint = {Kod(M)#Kod(M ) | L(M) ∩ L(M ) = ∅}
Prove that (Ldisjoint)Â
∈ LRE.
Exercise 7.
Prove that the following two functions are time-constructible:
(a) e(n) = 2n
,
(b) f(n) = fibn.
Here fibn denotes the n-th Fibonacci number, defined by fib0 = 0, fib1 = 1, and fibi =
fibi−2 + fibi−1 for i ∈ N≥2.
2