CSC363 UTM Winter 2024 Assignment 1 Due Wednesday January 31
You are not allowed to post the assignment questions anywhere; however, you are allowed to search the internet (just cite your resources if you find any). You are also allowed to bounce ideas off classmates and TAs, but at the end, you must write your own solutions.
Q1. In class we gave examples of the building rules composition and primitive recursion. In this question and the next one, you will learn the formal general definitions.
Composition: This building rule can possibly combine multiple functions together (if they have certain dimensions) to create a new function. It is common to think of composition as an operator, which is usually denoted by ◦.
Let h be a function from Nm to N (m ≥ 1 is a natural number), and let g1,…,gm be such that every gi is a function from Nk to N, where k ≥ 1 is a natural number. Notice that k is the same for all the functions g1, . . . , gm. Also notice that the number of functions gi (which is m) is exactly the number of arguments which the function h can take. From all these functions, we can build the following:
f(x1,…,xk) = h(g1(x1,…,xk),…,gm(x1,…,xk)). In terms of the operator ◦ we have
f =h◦(g1,…,gm).
In class, we looked at the very simple example of building f(x) = x + 2. In that simple
example, what are m, k, g1, and h?
Q2. Primitive Recursion: Now this building rule uses only two functions to create a new function. In some texts it is called the primitive recursion operator, and let’s denote it byρ. Givenafunctiong:Nk →N(k≥1natural),andafunctionh:Nk+2 →N,wecan build a new function f = ρ(g, h) from Nk+1 to N given by:
f(0,x1,…,xk) = g(x1,…,xk)
and, for every y ∈ N,
f(S(y),x1,…,xk) = h(y,f(y,x1,…,xk),x1,…,xk).
Informally, observe how f is defined at different levels (slices of its domain, Nk+1). At level 0 (on the 0th slice of Nk+1), the new function f acts exactly like g. Then, the behaviour of f on the y + 1th slice is described using h in terms of three things: y (the index of the previous slice), the yth slice itself, and the behaviour of f on the yth slice.
Inclass,welookedattheexamplef:N2 →Ngivenbyf(x1,x2)=x1+x2 (inotherwords, f = +). To show that f is primitive recursive, we need to show that f is obtainable from some other primitive recursive functions by means of recursion and composition. Formally prove that f is primitive recursive.
Programming Help, Add QQ: 749389476
CSC363 UTM Winter 2024 Assignment 1 Due Wednesday January 31
Q3. If you check the definition of the class PRIM on Wikipedia, you will see all constant functions (not only the zero function Z) are included as initial functions. This does not lead to a different class. So you believe me, prove that for an arbitrary natural k ≥ 1, and an arbitrary natural n, the constant function Cnk : Nk → N given by Cnk(x1, . . . , xk) = n is primitive recursive.
Hint: First prove that for all natural n, Cn1 is primitive recursive. You can use induction on n.
Q4. Let f : N → N be a computable function. Suppose that f is bijective. Prove that the inverse function to f is also computable.
Q5. Let f : N → N be a computable function. Prove that, for every x ∈ N, the set f−1(x) is decidable.
Q6. Prove that all the initial functions are computable by defining a Turing machine to compute each. For projections, since there are infinitely many of them, write a Turing machine specific for P23 (machines for other projections will be very similar).
Please write your machines as programs, where each line looks like qi x X qj (a quadruple) where x is either 1 or b, and X is one of 1, b, L (move left), or R (move right). Unlike the machine we defined in class, the one you will build here does not have movement happening together with writing/deletion in the same line.
Your program can terminate when there is no applicable quadruple, no need for a specific halting state.
Input convention: To input a natural value n, the tape will contain exactly n + 1-many of the symbol 1 contiguously (blanks elsewhere, unless there is more than one input). If there are multiple inputs, say (3,2,1), the tape then looks like . . . b1111b111b11b . . . where the dots are all b. The reading/writing head will be placed at the leftmost non-blank cell of the tape.
Output convention: The number of 1’s left on the tape when the program halts, they do not need to be contiguous.
Code Help, Add WeChat: cstutorcs