Computation Theory: the final course assignment
June 3, 2022
Choose seven questions from the list of questions below (choose at least two questions from the question 7 through the question 10) and solve them. Submit your answers by 23:59 on June 10 (Friday) to “final evaluation” on LMS. In the questions listed below, N denotes the set of natural numbers (non-negative integers).
Note: In the rigorous notation of recursive functions, you can use only the fundamental functions, the construction methods (composition, primitive recursion and minimization) and the functions already defined as recursive functions (and predicates) in Chapter 4. In your answers, you can use simplified notation shown in the slide “Simplified notation” in Chapter 4, as far as it’s clear that the simplified notation can be rewritten to the rigorous notation.
Copyright By PowCoder代写 加微信 powcoder
Similarly, you can use macro statements introduced in Chapter 5 and the while programs already defined in this course as sub-programs using function call macros.
Due to Theorem 6.4.1, if a function is defined in one computation model somewhere in this course or in your answers, you can use it in other computation models without having to define it explicitly (except when you are required to write the function in certain computation model in the questions below).
1. The Turing machine Mgt3 tests if x > 3 for a natural number x, such that the computation of Mgt3 with input BaxB terminates with state T if x > 3, with state F otherwise (the content of the tape does not matter when it terminates). Write Mgt3 as a quadruple (4-tuple), whose components are completely specified (Don’t use natural language to specify them).
2. Write a primitive recursive function that computes the integral part of square root of x ∈ N , i.e., ⌊√x⌋. (Hint: Use the bounded minimization.)
3. Write a while program divides(x, y) that computes the predicate x | y for any x, y ∈ N , where the program outputs 1 if x ̸= 0 and there exists a natural number z with 0 ≤ z ≤ y satisfying y = z · x; it runs forever if x = 0; it outputs 0 otherwise.
4. The binary representation of a natural number x with k bits is a sequence of 0 and 1’s of the k−1
form bk−1bk−2 . . . b1b0 that satisfies x =
bi · 2i, where bi is its i-th bit. Let bit(m, n) be
the function from N2 to N producing the n-th bit of the binary representation of m with k
bits if n < k; otherwise producing 0. Show that the function bit(m, n) is computable. (Hint: Describe the problem in some computation model.)
5. Write a RAM program that computes a recursive function h(x, y) = μz.p(z, x, y). You can assume that there exists a RAM program P (a sequence of instructions) which computes the predicate p so that you can write P in your RAM program when you want to use the sequence of instructions computing the predicate p. The RAM program P uses registers R(0), R(1), . . . , R(N ). The usage of registers in P follows the convention: each R(i) (1 ≤ i ≤ 3)
is used for the i-th argument of p and R(0) for the output of p. As in Definition 6.2.1, a label can be used to indicate the destination index of the J instruction. If you want to put a label, say L1, at the first instruction of P , write L1: P in your RAM program. (Hint: See the slide “Why minimization is computable ?” in Chapter 4.)
6. The function subI takes the codes of integers x and y, and outputs the code of x − y, where the code of an integer is obtained from the encoding introdued in Section 7.2. Show that subI is primitive recursive. (Hint: If x and y are integer, the property x − y = x + (−y) holds.)
7. Show that the primitive recursive function pair(x, y) = 2x · (2 · y + 1) − ̇ 1 in Definition 6.4.1, which encodes a pair of natural numbers in a natural number, is bijective. (Hint: Use the unique prime factorization theorem, as known as the fundamental theorem of arithmetic (https://en.wikipedia.org/wiki /Fundamental_theorem_of_arithmetic).)
8. We define that a single step execution of a while program is either the execution of a basic statement or the test of the condition of a while statement. Consider the problem to determine if a given while program P taking n inputs x1 , . . . , xn terminates in at most t steps. Show that this problem is decidable. (Hint: Give a while program step(x1, . . . , xn, ♯(P ), t) by modifying the universal while program universal(n).)
9. Show that a predicate φ(x1,...,xk) is decidable if and only if a predicate ¬φ(x1,...,xk) is decidable. (Hint: If φ(x1 , . . . , xk ) is decidable, there exists a while program with k input variables which terminates for any inputs x1,...,xk and outputs the value of φ(x1,...,xk)).
10. Let RetZeroInf be a unary predicate satisfying the following property: for an arbitrary unary while program P, RetZeroInf(♯(P)) holds if and only if the set {x | P with input x outputs 0 } is infinite. Show that RetZeroInf is undecidable. (Hint: Prove it using reduction to the halting problem. Hint2: If a while program with some inputs never terminate, then it doesn’t output any value.)
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com