hault and reducability

Question 1

Church and Turing thesis

Answer 1

Every function that can be calculated effectively, can be calculated using a Turing machine

Question 2

The H problem (halt0

Answer 2

H = {(p, w) | p(w) stops)
p - program, w - word

H is not decidable
proven using Cantor’s diagnal. We basically show that there is a series of outputs that can’t exist

Question 3

Is Halt acceptable

Answer 3

Yes, just run a simulation of p on w. The universal program accepts H.

Question 4

is Halt negative acceptable

Answer 4

No. If yes then using the Post theorem since Halt is also acceptable, halt would be decidable, which is wrong. Halt negative is a formal language.

Question 5

Reducibility

Answer 5

If there is a function f: Σ* -> Δ* that is computationally possible.
Given two languages L1∈Σ, L2∈Δ and
w∈L1 <-> f(w)∈L2
than: L1 <= L2

Question 6

Reducibility results

Answer 6

1: L2 decidable -> L1 decidable
2: L2 acceptable -> L1 acceptable
3: L1 not decidable -> L2 not decidable
4: L1 not acceptable -> L2 not acceptable

Question 7

Reducibility results if f(w)∉L2