Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

MAT309, PS2 First draft

The main focus of this problem set is on chapter 10 with selected definitions from chapters 8,9, 12 and 13.

1.    Prove Proposition 8.6.

2.    Given a structure m and a formula α such that m · α . What can you say about the relationship between Th({α}) and Th(m); is one subset of the other? Why?

3.    In each case below design a Turing Machine that performs the indicated action. Make sure your machine halts and returns the requested output, with the curse at the indicated cell of the tape.

a)  On an input of 01m 01k  it returns 01m+k+1  (Remeber in each case the rest of the tape consists of all

0.  (This means the SUM(m, k) function is Turing Computable.

b)  On the input of 01m 01k it returns 01k+1  (This means that the projection on the second component of an ordered pair is Turing Computable.)  (Hint: first carefully inspect Example 10.5, and do Problem 10.9.2.)

c)  On the input of 01m 01k  it returns 014  (This means that the constant function f(m, k) = 4 is Turing Computable.)

d)  Design the Turing Machine of Problem 12.1.4, the predecessor PRED(n) function.

e)  Composing Turing Machines: Suppose you are given a TM that is capable of writing n many 1 on a blank tape Use the instructions of this hypothetical TM to perform the following task: on the input of 01m 01k  it returns 0n + 1

4.    Read the link about Busy Beaver Contest.

https://webusers.imj-prg.fr/ pascal.michel/bbc.html

In the cases of 2 state and 3 state competitions, look at the design of the Turing machines and write the sequence of the sequence of tape positions and demonstrate how the maximum number 1 on the tape is acheived in each case.

Also see the following link: https://bbchallenge.org/story

5.     Consider definition of a TM (Definition 10.3) and use ideas similar to infinite hotel problems to prove there could be only countably many Turing Machines.

6.      Read Chapter 13, Definition 13.1.   (for k  =  1) This a generalization of a recursive construction of a function f with k + 1 (in this case with 2 inputs, f(x, n)):

.  Base case, 0, f(x, 0 is defined to be g(n)

.  Recursion/induction step: having constructed/defined f(x, m), we use the formula/function h(x, m, f(x, m))

to define f(x, m + 1).

Use this idea to define EXP (x, n) = xn  for two natural numbers x and n.