MATH 160A FALL 2022 Homework – week 5
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
MATH 160A
FALL 2022
Homework – week 5
Due by 2359 (11:59 PM) on Wednesday November 2. Hand in via Gradescope.
Note: For all problems, show your working and justify your answers. Upload all of your problems and working to the Gradescope assigment called “Full Paper Submission” . Additionally, upload your final answers only to the Gradescope assignment called “Answer-check Submission” for those problems marked [ACS] below.
You will not receive points for submitting answer to the Answer-check Submission if you do not also upload your working to the Full Paper Submission.
You may discuss these problems among yourselves, but your final submitted solutions must be written by you alone.
1. Fix an enumeration u0 , u1 , . . . of algorithms. Let h : N → N be the following function: h(n) =
Let f (n) = max0≤m≤n h(m).
(a) Prove that f is not computable.
[You may use the fact from lectures that the halting function H0 is non-computable.]
(b) Let F : N → N be any function such that F “eventually grows faster than f”: that is, there exists
N 2 0 such that for all n 2 N , F (n) 2 f (n).
Prove that F is not computable.
[In other words, “f grows faster than any computable function” .]
2. I have invented a cool new programming language, a variant of Python called Termisnakes. It has the following cool features:—
. Any valid Termisnakes program always terminates on every input.
. You are given an enumeration t0 , t1 , t2 , . . . that contains all valid Termisnakes programs (and
no invalid ones).
The details are proprietary but you should imagine that Termisnakes only allows for loops with a bound on the number of iterations given in advance, rather than general while loops which could run forever.
We say a function N → N is Termisnakes computable if there is a Termisnakes program whose output is that function. (By construction, such functions are total.)
Let T : N × N → N denote the universal Terminsnakes function T (n, a) = tn (a). Prove that T is not Termisnakes computable.
[Hint: assume for contradiction that it is, and carefully run through the same arguments that show that the halting problem is non-computable, adapted to this case.]
3. Consider the first-order language L(Ω, Π, α) with two function symbols Ω = {m, s} with arities α(m) = 1, α(s) = 0 and one relation symbol Π = {f } with arity α(f) = 2.
In natural language, we suppose the structure is a set of people, f (x, y) means “people x and y are friends”, and m(x) is “the mother of person x” and s is the constant “me” .
Find first-order formulae that denote the following English sentences.
(a) Everyone is friends with their mother but no-one is friends with themselves.
(b) Person x1 is a mother.
(c) I have at least, like, 1000 friends.
(d) Every mother has at least one friend who is the mother of a friend of one of their children. [Note: the conclusion should only apply to people who are mothers of children.]
(e) Any group of children with the same mother have a friend in common.
(f) Any friend of a friend of my grandmother is a friend of mine!
4. In lectures I incorrectly stated that < was a relation symbol in Peano Arithmetic / formal number theory. In fact it is a shorthand:
x < y 4 (3z)(a(x, z) = y).
(Recall the structure here is N, not Z.) You may use this shorhand if you wish.
Find formulae in the (revised) language of Peano Arithmetic to encode the following statements.
(a) x3 is the highest common factor of x1 , x2 .
(b) x2 =「^x1|.
2022-11-03