Theoretical Computer Science (M21276)
Part B/3: Diagonalisation and the Halting problem
(Dec 6 – Dec 10, 2021)
Question 1.[Librarian paradox] Figure out, where is the problem:
Copyright By PowCoder代写 加微信 powcoder
Some books mention themselves in the book; many books, do not. An unfortunate library intern is given the task of creating a new book, which will contain list of all books in the library that do not mention themselves. She toils all summer. In the end, she has a list. This she triumphantly adds to the reference section as the new book “Non Self-Monitoring Books”. She is about to head back to campus, when the head librarian asks, “Shouldn’t your book itself be added to the list?”. . .
Other paradoxes.
Socratic paradox: “I know that I know nothing at all.”
Russell’s paradox: “ Does the set of all those sets that do not contain themselves
contain itself?”
Liar paradox: “This sentence is false.” or “Is the answer to this question no?” or “I’m lying.”
Question 2. Discuss whether the following sets are countable or uncountable:
(a) the set of negative integers,
(b) the set of odd positive integers,
(c) the set of all positive and negative integers,
(d) the set of all positive rational numbers (fractions),
(e) the set of real numbers, (f) the set of strings over {a},
(g) the set of all languages over the alphabet {a},
(h) the set of all languages over the alphabet {a, b, c, d, e, f, g, h, i, j},
(i) the set of all languages over the alphabet {1, 2, 3, . . . } = N,
(j) the set of all strings over a finite alphabet Σ,
(k)foreachn∈N,thesetAn ofallstringsinA∗ havinglengthn,whereAisa
countable infinite alphabet A = {a0,a1,…,an,…}, (l) the set of all total functions from N → {0, 1},
(m) the set of all total functions from N → {1}, (n) the set of all total functions from {0, 1} to N.
Answer: All sets except (e), (g), (h), (i), (l) are countable. Consider the matching with the set N (a) 1 → −1, 2 → −2, 3 → −3, . . . ; (b) 1 → 1, 2 → 3, 3 → 5, 4 → 7, . . . ; (c) 1→ 1, 2 → −1, 2 → 2, 3 → −2, 4 → 3, 5 → −3, …; (k) for each natural number k, let Sk be the set of strings of length n over the alphabet {a0, a1, . . . , ak}. It follows that An = S0 ∪ S1 ∪ ··· ∪ Sn ∪ …. Since each set Sn is finite, hence countable, the union is countable, (l) uncountable, for each subset of N we can define two different functions – and there are uncountable many subsets of P(N), (m) there is only one such function, hence countable, no) similar to (d) – consider all possible pairs.
Question 3. Show how diagonalisation produces a string not on the following list: EVERY
CLIFF KNEAD
Question 4. Ackermann function is an example of the computable function, which is not primitive recursive. Can you give another proof of the existence of the computable function, which is not primitive recursive?
(Hint: Find out how many primitive recursive functions there exist and then use a diag- onalisation argument)
Answer: We can use a diagonalisation argument. Each primitive recursive function is given by a finite string. Therefore, we can number them f1, f2, . . . . Define a function g by
g(x) = fx(x) + 1.
This g is perfectly computable function. But it cannot be primitive recursive for the same
old reason: it is different from each primitive recursive function.
Question 5. Assume that we have an enumerated list of computable functions: f0, f1,
f2, . . . , fi, . . . Show that the following function is computable:
h(x) = 1, if fx halts on input x, otherwise loops forever.
Answer: Since fx is a computable function, we can compute h(x) by running the algo- rithm to find fx(x). If the algorithm halts, then return h(x) = 1. If the algorithm does not halt, we’re still OK as we want h(x) to run forever.
Question 6. Show that the problem of deciding whether two deterministic finite au- tomata over the same alphabet accept the same languages is solvable. (Unlike the problem of whether two Turing machines are equivalent, which is not solvable.)
Answer: In THCSA, we showed how to find a minimum state DFA that recognised the same language as any arbitrary DFA. According to the Myhill-Nerode theorem, this DFA
is unique, modulo a trivial renaming of states. To determine if two DFAs accept the same language, we simply must reduce each to its minimum state DFA and see if they are the same. Do they have the same number of states? If so, is there a one to one correspondence between their transitions?
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com