3. Метод резолюций в логике высказываний

Доказать истинность следующих высказываний методом резолюций.

1.18. ⊢(pr);

Получен нулевой элемент следовательно высказывание истинно.

1.2.

Получен нулевой элемент следовательно высказывание истинно.

4. Элементы теории алгоритмов

1. Выяснить, применима ли машина Тьюринга Т, задаваемая программой П, к слову Р. Если применима, то найти результат применения машины Т к слову Р. Предполагается, что q₁ * начальное состояние, q₀ * заключительное состояние и в начальный момент головка машины обозревает самую левую единицу на ленте.

1.1

c) P = 1³01^3.

q₁1³01³⊢1³q₁01³⊢ 1³0q₂1³⊢ 1³01q₁1²⊢ 1³01³ q₁

Машина неприменима, так как не может закончить свою работу.

2 По заданной машине Тьюринга т и начальной конфигурации к1 найти заключительную конфигурацию (q0 * заключительное состояние).

2.2

a) K₁= 1q₁1⁵,

1q₁1⁵⊢11q₂1⁴⊢110q₃1³⊢1100q₁1²⊢11001q₂1⊢110010q₃0 ⊢11001q₁01 ⊢11001q₀01

3. Построить композицию т1т2 машин Тьюринга т1 и т2 (по паре состояний (q10, q21)) и найти результат применения композиции t1t2 к слову p (q20 - заключительное состояние машины т2), если

3.1. программы машин Т₁ и Т₂ заданы таблицами:

T1:		q11	q12	q13	T2:		q21	q22
	0	q100L	q130R	q110R		0	q221Ll	q200R
	1	q121R	q131R	q110R		1	q221L	q210L

a)P = 1⁴0²1³01²,

	0	1
q11	q221L	q121R
q12	q130R	q131R
q13	q110R	q110R
q21	q221L	q221L
q22	q200R	q210L

q₁₁1⁴0²1³01²⊢ 1q₁₂1³0²1³01²⊢ 11q₁₃1²0²1³01²⊢ 110q₁₁10²1³01²⊢ 1101q₁₂0²1³01²⊢ 11010q₁₃01³01²⊢ 110100q₁₁1³01²⊢ 1101001q₁₂1²01²⊢ 11010011q₁₃101²⊢ 110100110q₁₁01²⊢ 110100110q₂₁01²⊢ 11010011q₂₂01³⊢ 110100110q₂₀1³

6 Написать программу машины Тьюринга, складывающую натуральные числа, записанные в унарной системе счисления, т.е. машину Т, удовлетворяющую условию: Т((m)_унарн.+(n)_унарн.) = (m+n)_унарн. Привести пример сложения.

˄q₁1³+1²˄⊢ ˄1³q₁+1²˄⊢ ˄1³˄q₂1²˄⊢ ˄1³q₃˄+1˄⊢ ˄1⁴q₁+1˄⊢ ˄1⁴˄q₂1˄⊢ ˄1⁴q₃˄+˄⊢ ˄1⁵ q₁+˄⊢ ˄1⁵ ˄q₂˄⊢ ˄1⁵ ˄q₀˄