TOA Test Two

Question 1

Initial functions

Answer 1

The constant 0, the zero function of variable z(x)=0, the successor function s(x)=x+1, and the projective functions defined by Ink=(x1,…,xn)=xk

Question 2

Primitive recursion

Answer 2

The operation that takes a function G: N^n→N & a function h: N^(n+2)→N and produces a function f→N^(n+1)→N by setting f= g(x,0) and f(x, s(y))=h(x,y,f(x,y))

Here x=

Question 3

Partial function f

Answer 3

N→N is allowed to be undefined for some values n ∈ ℕ

Question 4

μ - recursive function

Answer 4

A partial function that can be obtained from the initial functions using the operations of Cartesian product, composition, primitive recursion and minimization on total functions.

Question 5

Turing-computable partial-function from N to N

Answer 5

A partial function f: ℕ→ℕ is Turing computable if we can find a TM M such that M halts in an accepting state with output f(n) ⇔n ∈dom(f)

Question 6

Busy-beaver function β(n)

Answer 6

β(n)= maximum number of 1’s that a TM in Hn can produce when started on the blank tape.

Question 7

Turing-decidable language

Answer 7

A language L is turing-decidable if we can find a TM M,such that M1 halts on ω in an accepting state, if ω ∈L and M1 halts on ω in an non-accepting state, if ω ∉L

Question 8

Turing semi-decidable

Answer 8

L is Turing semi-decidable if we can find a TM M2 such that M2 halts in an accepting, if ω ∈L and M2 halts on ω in a non-accepting state or fails to halt, if ω ∉L

Question 9

R on N^k to be Turing decidable

Answer 9

R ⊆N^k is turing-decidable if we can find a TM M such that on the input x; m will halt in an accepting state it x∈R, and M will halt in a non-accepting state if x∉R

Question 10

Define what it means for a function f: D→ℕ to be Turing computable

Answer 10

f: D→ℕ is turing-computable if we can find a TM M such that ω∈D⇔⟨q0, ω⟩⊢⟨qF,f(ω)⟩ is halted computation in M with qF ∈A(M)

Question 11

Minimization

Answer 11

The operation that produces a partial function f:ℕ^n →ℕ from total function g:ℕ^n+1 →ℕ by setting f(x)= {The smallestof y such that g(x,y)=0
Undefined, if there is no value of y s.t g(x,y)=0

Question 12

Turing semi-decidable relation ℝ on ℕ

Answer 12

A relation R⊆ℕ×ℕ is Turing semi-decidable if we can find a TM M such that M halts on ⟨m,n⟩ in an accepting state if ⟨m,n⟩ ∈R and M halts on ⟨m,n⟩ in a non-acc. State or M fails to halt if ⟨m,n⟩ ∉R

Question 13

Pumping Lemma

Answer 13

Suppose L is a infinite regular language . Then we can find an m∈ℕ such that any string ω∈L with |ω|≥m can be decomposed as ω=xyz such that |xy|≤m, |y|≥1 and xy^iz∈L for each i∈ℕ

Question 14

Composition

Answer 14

The operation that produces a function f:N^n→N from g1,…,gk:N^n→N and h:N^k→N by putting f(x)=h(g1(x),…,gk(x)). Here x=