По теории алгоритмов Построить МТ (машину Тьюринга), которая обращает любое входное слово в заданном алфавите.

По теории алгоритмов Построить МТ (машину Тьюринга), которая обращает любое входное слово в заданном алфавите. Указание: используйте программу МТ, удваивающей заданное слово, и сочетания МТ

Составим программу для машины Тьюринга в виде таблицы, A=a,b,=,λ
Q
λ (пустая
ячейка) a
b
=
q0
q1=,L
q0a,R
q0a,R
q1
qfλ,S
q2λ,R
q4λ,R
q2
q3a,L
q2a,R
q2b,R
q2=,R
q3
q1a,L
q3a,L
q3b,L
q3=,L
q4
q5b,L
q4a,R
q4b,R
q4=,R
q5
q1b,L
q5a,L
q5b,L
q5=,L
Описание: головка машины стоит над любым символом слова, после чего находит его конец, ставит знак = и дублирует слово с конца .
Программа в виде команд:
q0a→q0a,R
q0b→q0a,R
q0λ→q1=,L
q1a→q2λ,R
q2a→q2a,R
q2=→q2=,R
q2b→q2b,R
q2λ→q3a,L
q3=→q3=,L
q3a→q3a,L
q3b→q3b,L
q3λ→q1a,L
q1b→q4λ,R
q4=→q4=,R
q4a→q4a,R
q4b→q4b,R
q4λ→q5b,L
q5=→q5=,L
q5a→q5a,L
q5b→q5b,L
q5λ→q1b,L
q1λ→qfλ,S
Задача по математической логике
Доказать в исчислении высказываний (буквы обозначают произвольные формулы):
((A B) C) A (BC)
Все равносильности можно проверить таблично
A
B
C
A
B
A B
(A B)
(A B) C
BC
A (BC)
0 0 0 1 1 1 0 1 1 1
0 0 1 1 1 1 0 1 1 1
0 1 0 1 0 1 0 1 0 1
0 1 1 1 0 1 0 1 1 1
1 0 0 0 1 1 0 1 1 1
1 0 1 0 1 1 0 1 1 1
1 1 0 0 0 0 1 0 0 0
1 1 1 0 0 0 1 1 1 1
Рассмотрим левую часть, перейдем к операциям конъюнкции и дизъюнкции и инверсии:
¬¬A→¬B ∨ C
¬A∨¬B ∨C
¬A∨¬B∨C
Рассмотрим правую часть, перейдем к операциям конъюнкции и дизъюнкции и инверсии:
¬A∨¬B∨C
¬A∨¬B∨C
Получим, ¬A∨¬B∨C≡¬A∨¬B∨C

.
Программа в виде команд:
q0a→q0a,R
q0b→q0a,R
q0λ→q1=,L
q1a→q2λ,R
q2a→q2a,R
q2=→q2=,R
q2b→q2b,R
q2λ→q3a,L
q3=→q3=,L
q3a→q3a,L
q3b→q3b,L
q3λ→q1a,L
q1b→q4λ,R
q4=→q4=,R
q4a→q4a,R
q4b→q4b,R
q4λ→q5b,L
q5=→q5=,L
q5a→q5a,L
q5b→q5b,L
q5λ→q1b,L
q1λ→qfλ,S
Задача по математической логике
Доказать в исчислении высказываний (буквы обозначают произвольные формулы):
((A B) C) A (BC)
Все равносильности можно проверить таблично
A
B
C
A
B
A B
(A B)
(A B) C
BC
A (BC)
0 0 0 1 1 1 0 1 1 1
0 0 1 1 1 1 0 1 1 1
0 1 0 1 0 1 0 1 0 1
0 1 1 1 0 1 0 1 1 1
1 0 0 0 1 1 0 1 1 1
1 0 1 0 1 1 0 1 1 1
1 1 0 0 0 0 1 0 0 0
1 1 1 0 0 0 1 1 1 1
Рассмотрим левую часть, перейдем к операциям конъюнкции и дизъюнкции и инверсии:
¬¬A→¬B ∨ C
¬A∨¬B ∨C
¬A∨¬B∨C
Рассмотрим правую часть, перейдем к операциям конъюнкции и дизъюнкции и инверсии:
¬A∨¬B∨C
¬A∨¬B∨C
Получим, ¬A∨¬B∨C≡¬A∨¬B∨C