Студопедия  
Главная страница | Контакты | Случайная страница

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

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

Читайте также:
  1. C. Ветвящихся алгоритмов
  2. I. Исторические аспекты возникновения теории инвестиций и инвестиционного менеджмента.
  3. I. Исторические аспекты возникновения теории инвестиций и инвестиционного менеджмента.
  4. I. Основные парадигмы классической социологической теории.
  5. I. Социальное взаимодействие и социальное отношение. Теории социального взаимодействия.
  6. I. Теории социального неравенства.
  7. I.II. ЭЛЕМЕНТЫ ФИНАНСОВОЙ ПОЛИТИКИ
  8. II Отказ от предположений неоклассической теории
  9. II. Методология теории государства и права.
  10. II. Неклассическая парадигма социологической теории.

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

1.1.

a) Р=10[01]21. b) P = 130212, c) P = 13013.

1.2.

a) P=13012, b) P = 16, c) P= 1401.

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

2.1.

  T:   q1 q2
q01S q10R
q20R q21L

 

а) К1 = 12q11301, b)K1 = 1q114.

 

2.2.

a) K1= 1q115, b) K1 = q11301, c) K1 = 10q114.

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

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

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

 

a)P = 140213012, b) P = 1201013.

3.2.

a) P = 12013012, b) P = 120120212.

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

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

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

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


Дата добавления: 2014-11-24; просмотров: 24 | Нарушение авторских прав




lektsii.net - Лекции.Нет - 2014-2017 год. (0.011 сек.)