Языки и трансляции. Мартыненко Б.К. - 104 стр.

UptoLike

ВУЗ: 

СПбГУ | Санкт-Петербург

Составители: 

Рубрика: 

103
I-6.4. Построить машины Тьюринга любой разновидности, которые распоз-
нают множества:
a) {0
n
1
n
2
n
n ≥ 1}.
b) Множество слов из {0, 1}
*
, двоичные значения которых равны квадратам
совершенных чисел.
c) L = {0
i
10
j
10
k
10
m
m ≥ 3 и i
m
+ j
m
= k
m
}.
Язык L представляет недоказанную гипотезу Ферма в теории чисел:
“Для m ≥ 3 не существует целочисленного решения уравнения i
m
+ j
m
= k
m
”.
Таким образом, язык L пуст, если, и только если, гипотеза Ферма выполняется.
К сожалению, не существует алгоритма для определения, принимает ли
произвольная машина Тьюринга хотя бы один вход. Если бы такой алгоритм
существовал, то он мог бы быть применён к машине Тьюринга, распознающей
язык L, и гипотеза Ферма была бы разрешена.
d) Множество арифметических выражений в языке Паскаль.
e) {a
i
i совершенное число
10
}.
I-6.5. Дать полное доказательство теоремы 6.6.
I-6.6. Показать, что магазинный автомат эквивалентен машине Тьюринга с
входом только для чтения, на котором он может двигаться только вправо или
оставаться неподвижно. Эта машина Тьюринга недетерминированная и имеет
одну ленту памяти. Всякий раз, как эта машина Тьюринга движется влево, она
должна печатать пробел.
I-6.7. Показать, что если L распознаётся машиной с одним счётчиком и
входной лентой, читаемой в одном направлении, то L cfl.
I-6.8. Показать, что каждая Tm эквивалентна одно-ленточной Tm с одним
принимающем и двумя не принимающими состояниями.
I-6.9. Существует ли Tm, которая может диагонализировать над всеми
машинами Тьюринга? Если бы существовал алгоритм, определяющий, остано-
вится ли произвольная Tm с произвольный вводом, могла бы некоторая Tm
диагонализировать над всеми машинами Тьюринга?
10
Совершенное число есть целое, равное сумме всех своих делителей, исключая его самого.
Так 6
совершенное число, так как 1 + 2 + 3 = 6. Число 12 не является совершенным,
поскольку его делители 1, 2, 3, 4 и 6, и их сумма 16.

Страницы