Постройте машину Тьюринга,

Постройте машину Тьюринга, осуществляющую перевод натурального числа n

a) из двоичной системы в троичную. Начальная конфигурация: q1a1a2…an, заключительная конфигурация: q0b1b2…bm, где ai – двоичные цифры 0, 1; bi – троичные цифры 0, 1 или 2;

a) из двоичной системы в десятичную. Начальная конфигурация: q1a1a2…am, заключительная конфигурация: q0d1d2…dn, где ai – двоичные цифры 0, 1; di – десятичные цифры 0, 1, …, 9;

b) из восьмеричной системы счисления в двоичную с использованием метода триад. Начальная конфигурация: q1c1c2…cn, заключительная конфигурация: q0a1a2…am, где ai – двоичные цифры 0, 1; ci – восьмеричные цифры 0, 1, …, 7;

c) из троичной системы в двоичную. Начальная конфигурация: q1b1b2…bm, заключительная конфигурация: q0a1a2…an, где ai – двоичные цифры 0, 1; bi – троичные цифры 0, 1 или 2;

d) из двоичной системы счисления в восьмеричную с использованием метода тетрад. Начальная конфигурация: q1a1a2…am, заключительная конфигурация: q0c1c2…cn, где ai – двоичные цифры 0, 1; ci – восьмеричные цифры 0, 1, …, 7;

0) находящую и выделяющую (например, «*») первое вхождение слова log в произвольное слово Р в алфавите {l, o, g} или сообщающую о том, что такого вхождения нет;

1) переводящую слово F в алфавите {a, b, c} в его «зеркальное отражение» F~. Начальная конфигурация: q₁F, заключительная конфигурация: q₀F~. (Например, слово abbca эта машина должна переводить в слово acbba, слово baba - в слово abab и т.д.);

2) находящую и выделяющую (например, «?») первое вхождение слова dec в произвольное слово G в алфавите {d, e, c} или сообщающую о том, что такого вхождения нет;

3) строящую инверсию двоичного кода a₁a₂…a_n. Начальная конфигурация: q₁a₁a₂…a_n, заключительная конфигурация: q₀a’₁a’₂…a’_n, где a’_i=1, если a_i=0 и a’_i=0, если a_i=1;

4) находящую и выделяющую (например, «%») первое вхождение слова int в произвольное слово W в алфавите {i, n, t} или сообщающую о том, что такого вхождения нет;

5) проверяющую справедливость неравенства n > m, где n и m - двоичные числа. В зависимости от справедливости неравенства, машина слева от него пишет на ленте "ДА" или "НЕТ". Начальная конфигурация: q₁b₁b₂…b_s > y₁y₂…y_t, заключительная: q₀Pb₁b₂…b_s > y₁y²…y_t, где y_i, b_iÎ{0,1}, PÎ{ДА, НЕТ};

6) находящую и выделяющую (например, «#») первое вхождение слова abs в произвольное слово V в алфавите {a, b, s} или сообщающую о том, что такого вхождения нет;

7) проверяющую справедливость неравенства n < m, где n и m - двоичные числа. В зависимости от справедливости неравенства, машина слева от него пишет на ленте "ДА" или "НЕТ". Начальная конфигурация: q₁b₁b₂…b_s < y₁y₂…y_t,, заключительная: q₀Pb₁b₂…b_s < y₁y²…y_t, где y_i, b_iÎ{0,1}, PÎ{ДА, НЕТ};

8) находящую и выделяющую (например, «$) первое вхождение слова sqr в произвольное слово Q в алфавите {s, q, r} или сообщающую о том, что такого вхождения нет;

9) переводящую слово H в алфавите {e, x, p} в его «зеркальное отражение» H~. Начальная конфигурация: q₁H, заключительная конфигурация: q₀H~. (Например, слово eexxp эта машина должна переводить в слово pxxee).

Рекомендуемая литература

1.	Ершов Д.Л., Палютин Е.А. "Математическая логика", М, Наука, 1987г.
2.	Карпов В.Г., Мощенский В.А. Математическая логика и дискретная математика. – Минск: «Вышэйш. школа», 1977
3.	Клини С. Математическая логика. - М.: Мир, 1980.
4.	Колесников Н.Г. Математические и логические основы информатики. Краснодар: КубГАУ, 2000
5.	Колмогоров А.Н. Математика / В кн. Колмогоров А.Н. Математика в её историческом развитии. - М.: Наука, 1991. - С.
6.	Колмогоров А.Н., Драгалин А.Г. Введение в математическую логику. - М.: Изд-во МГУ, 1982.
7.	Кук Д., Бейз Г. "Компьютерная математика", М, Наука, 1990г.
8.	Куратовский К., Мостовский А. Теория множеств. М., 1970
9.	Лихтарников Л.М, Сукачева Т.Г. Математическая логика. - СПб: Изд-во «Лань», 1998
10.	Столяр А.А. Элементарное введение в математическую логику - М.: Изд-во «Просвещение», 1965

Дата добавления: 2014-11-20