Advertisement
Guest User

Untitled

a guest
Jun 25th, 2017
59
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.54 KB | None | 0 0
  1. 3) a) Un is computed by: X = φ^n (X_1,…X_n,X_(n+1))
  2. b) By the Universiality Theorem 3.1, since Un can be written in L, it is defined (See part a.). Also since x = #(P), then Un computes Φ^1 (x,x) and so Φ^1 (x,x) is partially computable. Since it is partially computable, H(x) is partially computable.
  3.  
  4. According to Theorem Un is used to compute partially computable functions since Un computes Φ(x,x)(Part 3a) then Φ(x,x) must be partially computable therefore the function is defined. Since Φ(x,x) is defined H(1) is partially computable.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement