Задание №7. Доказать примитивную рекурсивность функций, выражая их через простейшие с помощью операторов

Доказать примитивную рекурсивность функций, выражая их через простейшие с помощью операторов

суперпозиции и примитивной рекурсии.

f(x) = 2x+1;

Доказательство ПРФ:

I₁¹(x)= 2*0+1= 1;

S (I₃³(x, y, z)) = f(x+1)= (x+1)+(x+1)+1= 2x+3;

Задание №8

Построить машины Тьюринга для вычисления функций.

f(x)= 2x+1;

Решение:

_q1

q₁01^x00… ® q₀01^2x+10…

Построение машины Тьюринга для вычисления функции f(x)= 2x+1:

0q₁ ® Rq₂;

1q₂ ® Rq₂;

0q₂ ® Rq₃;

0q₃ ® 1q₄;

1q₃ ® Rq₃;

1q₄ ® Lq₄;

0q₄ ® 1q₅;

1q₅ ® Lq₆;

1q₆ ® 0q₆;

0q₆ ® Lq₇;

1q₇ ® 1q₂;

0q₇ ® Rq₈;

0q₈ ® 1q₉;

1q₉ ® Lq₀;

1 Из данной совокупности секвенций выбрать доказуемые, построить их доказательства, для недоказуемых показать их недоказуемость с помощью: а) алгоритма Квайна; б) алгоритма редукции; в) метода резолюций. Среди этих доказательств недоказуемости выбрать оптимальное в каждом конкретном случае.

а) (y ۸ z)⊦ y ۷ z

Промежуточная секвенция: ⊦ φ ۷ φ

φ ⊦ φ (φ ۷ φ) ⊦ (φ ۷ φ)

(φ ۷ φ), φ ⊦

(φ ۷ φ) ⊦ φ ۷ φ; (φ ۷ φ) ⊦ (φ ۷ φ)

(φ ۷ φ) ⊦

⊦ φ ۷ y

Доказательство правила вывода Γ, φ ۸ ψ ⊦ χ

Γ, φ, ψ ⊦ χ

Γ, φ ۸ ψ, φ ⊦ ψ; Γ, φ ۸ ψ, φ ⊦ ψ  x

Γ, φ ۸ ψ ⊦ χ

y ۸ z ⊦ y ۸ z (y ۸ z) ⊦ (y ۸ z)

(y ۸ z), y ۸ z ⊦ y ۸ z; (y ۸ z), y ۸ z ⊦ (y ۸ z)

(y ۸ z), y, z ⊦ y ۷ z; (y ۸ z), y, z ⊦ y ۷ z; (y ۸ z) ⊦ z ۷ z

(y ۸ z), y ⊦ y ۷ z y ⊦ y ⊦ y ۷ y

(y ۸ z), y ⊦ y ۷ z (y ۸ z), y ⊦ y ۷ z (y ۸ z) ⊦ y ۷ y

(y ۸ z)⊦ y ۷ z

б) x ۷ y, x ۷ z, x ۷ z ۷ u ⊦ u ۷ y

Секвенция недоказуема.

· Алгоритм Квайна.

(x ۷ y) ۸ (x ۷ z) ۸ (x ۷ z ۷ u) ⊦ (u ۷ y)

Пусть x = 1

(1 ۷ y) ۸ (1 ۷ z) ۸ (1 ۷ z ۷ u) ⊦ (u ۷ y)

1 ۸ 1 ۸ 1 ⊦ (u ۷ y)

1 ⊦ (u ۷ y)

Пусть u = 0

1 ⊦ y

Пусть y = 0

1 ⊦ 0  противоречие. Секвенция недоказуема.

· Алгоритм редукций.

(x ۷ y) ۸ (x ۷ z) ۸ (x ۷ z ۷ u) = 1

(u ۷ y) = 0  верно, при u = 0 и y = 0

(x ۷ 0) ۸ (x ۷ z) ۸ (x ۷ z ۷ 0) = 1

x ۸ (x ۷ z) ۸ (x ۷ z) = 1

При x = 1:

1 ۸ (1 ۷ z) ۸ (1 ۷ z) = 1 z – любое

z – любое  1 = 1

При x = 1, y = 0, u = 0 секвенция недоказуема.