Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

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

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

1.1.

a) Р=10[01]²1. b) P = 1³0²1², c) P = 1³01^3.

1.2.

a) P=1³01², b) P = 1⁶, c) P= 1⁴01.

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

2.1.

а) К₁ = 1²q₁1³01, b)K₁ = 1q₁1⁴.

2.2.

a) K₁= 1q₁1⁵, b) K₁ = q₁1³01, c) K₁ = 10q₁1⁴.

a. Построить композицию Т₁Т₂ машин Тьюринга Т1 и Т2 (по паре состояний (q₁₀, q₂₁)) и найти результат применения композиции T₁T₂ к слову P (q₂₀ - заключительное состояние машины Т₂), если

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

a)P = 1⁴0²1³01², b) P = 1²0101³.

3.2.

a) P = 1²01³01², b) P = 1²01²0²1².

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

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

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

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