Главная Случайная страница


Полезное:

Как сделать разговор полезным и приятным Как сделать объемную звезду своими руками Как сделать то, что делать не хочется? Как сделать погремушку Как сделать так чтобы женщины сами знакомились с вами Как сделать идею коммерческой Как сделать хорошую растяжку ног? Как сделать наш разум здоровым? Как сделать, чтобы люди обманывали меньше Вопрос 4. Как сделать так, чтобы вас уважали и ценили? Как сделать лучше себе и другим людям Как сделать свидание интересным?


Категории:

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






Задачи. 1. По заданной машине Тьюринга и начальной конфигурации найти заключительную конфигурацию:





 

1. По заданной машине Тьюринга и начальной конфигурации найти заключительную конфигурацию:

1) ; .

2) ; .

3) ; .

4) ; .

5) ; .

6) ; .

7) ; .

8) ; .

9) ; .

10) ; .

 

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

1) ; а) ; б) .

2) ; а) ; б) .

3) ; а) ; б) .

4) ; а) ; б) .

5) ; а) ; б) .

 

3. Построить в алфавите {0,1} машину Тьюринга, обладающую свойствами:

1) машина имеет одно состояние, одну команду и применима к любому слову в алфавите {0,1};

2) машина имеет одно состояние, две команды, не применима ни к какому слову в алфавите {0,1}, и в процессе работы головка обозревает бесконечное множество ячеек;

3) машина имеет две команды, не применима ни к какому слову в алфавите {0,1}, и в процессе работы головка обозревает одну ячейку.

Предполагается, что в начальный момент времени головка машины обозревает самый левый символ слова.

 

4. По словесному описанию машины Тьюринга построить ее программу (в алфавите {0,1}).

1) Начав работу с первой единицы массива из единиц, машина “сдвигает” его на две ячейки вправо, не изменяя остального содержимого ленты, и останавливается на последней единице перенесенного массива.

2) Начав двигаться влево от произвольной ячейки, головка находит первую при таком перемещении ячейку с единицей (если такая встретится на пути) и, сделав один шаг вправо, останавливается на соседней ячейке. Содержимое ленты не меняется.

3) Машина начинает работу с самой левой непустой ячейки и отыскивает нуль, примыкающий с левой стороны к первому справа массиву из трех единиц, окаймленному нулями. Головка останавливается на первой единице найденного массива (если такой есть). Содержимое ленты не меняется.

4) Головка машины, начав работу с произвольной ячейки, содержащей единицу, двигается влево до тех пор, пока не пройдет подряд пять нулей. Головка останавливается на первой ячейке слева за этими пятью нулями, напечатав в ней единицу. Остальное содержимое ленты не меняется.

5) При заданном головка машины, начав работу с произвольной ячейки и двигаясь вправо, записывает подряд нулей и останавливается на последнем из них.

6) Головка машины, двигаясь вправо от какой-либо пустой ячейки, находит первый при таком перемещении массив, содержащий не менее семи единиц, стирает в нем первые семь единиц и останавливается на самой правой из ячеек, в которых были стерты единицы. Остальное содержимое ленты не меняется.

7) При заданном значении n головка машины из n записанных единиц оставляет на ленте единицы, так же записанных подряд, если , и работает вечно, если или .

8) Машина реализует алгоритм вычисления функции , считая, что число n представляется записанными подряд n единицами, и массив из n единиц уже найден.

9) Машина реализует алгоритм вычисления функции , считая, что число n представляется записанными подряд n единицами, и массив из n единиц уже найден.

10) Машина реализует алгоритм вычисления функции

Считается, что число n представляется записанными подряд n единицами, и массив из n единиц уже найден.

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

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

 

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

 

6. Построить композицию машин Тьюринга и по паре состояний (, ) и найти результат применения композиции к слову .

1)      
:   , :  
       

а) ; б) .

 

2)  
:  
   

 

   
:  
   

а) ; б) .

 

3)  
:  
    -

 

   
:  
   

а) ; б) .

 

7. Найти результат применения итерации машины по паре состояний (, ) к слову (заключительными состояниями являются и ).

1)

   
:  
    - -

а) ; б) .

 

2)

   
:  
   

а) ; б) .

 

В Ответы и указания.

В Содержание.

 

 

Ответы и указания.

 

Глава 1. Высказывания, формулы, тавтологии. 2. 2), 5), 8), 10) – истинные высказывания. 1), 4), 7) – ложные высказывания. 3), 6) высказываниями не являются. 3. Обратите внимание, что 7) – составное высказывание. 5. Не являются тавтологиями: 2), 3), 5). Вернуться в Задачи.

Глава 3. Исчисление высказываний. 1. 1), 2), 5), 7), 8), 9) – формулы исчисления высказываний. 3), 4), 6), 10) формулами исчисления высказываний не являются. 2. 2). 3. 5) Применить лемму. 6), 7), 9) – применить результат 5). 8), 10), 11), 12) – применить результат 9). Вернуться в Задачи.

Глава 5. Предикаты. 1. 1) . 3) . 5) . 7) . 8) . 9) . 10) . 2. 1), 3), 4), 6), 7), 9), 10). 1. 2), 5), 8). 0. 3. 7) Воспользоваться формулой .

4. 1) .

2) . 3) .

4) . 5) .

6) . 7) .

8) .

9) .

10) . 8. Можно привести такой пример: , . Предикаты рассматриваются на множестве . Вернуться в Задачи.

Глава 8. Рекурсивные функции. 1. 1) . 2) .

3) 4) . 5) . 6) . 7) .

8) 9)

10) Вернуться в Задачи.

Глава 9. Машины Тьюринга. 1. 1) . 2) . 3) . 4) . 5) . 6) . 7) . 8) . 9) .

11) . 2. 1) а) ; б) . 2) а) Неприменима;

б) . 3) а); б) Неприменима. 4) а) ; б) Неприменима. 5) а) Неприменима; б) . 6. 1) а) ; б) . 2) а) ;

б) . 3) а) ; б) . 7. 1) а) ; б) . 2) а) ; б) . Вернуться в Задачи.

 

В Содержание.

 

Литература.

1. Бочкарева О.В. Учебное пособие по математике (специальные главы). М., Радио и связь, 2001.

2. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по курсу дискретной математики. М., Наука, 1992.

3. Горбатов В.А. Фундаментальные основы дискретной математики. М., Наука, 2000.

4. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженеров. М., Энергоатомиздат, 1988.

5. Кук Д., Бейз Г. Компьютерная математика. М., Наука,1990.

6. Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. М., ФИЗМАТЛИТ, 2001.

7. Логинов Б.М. Введение в дискретную математику. Калуга, 1998.

8. Лихтарников Л.М., Сукачева Т.Г. Математическая логика. Курс лекций. Задачник-практикум и решения. СПб, Лань, 1999.

9. Математическая энциклопедия. Т. 1. М., Советская Энциклопедия, 1977.

10. Мендельсон Э. Введение в математическую логику. М., Наука, 1984.

11. Непейвода Н.Н. Прикладная логика. Новосибирск, Изд-во Новосибирского университета, 2000.

12. Новиков Ф.А. Дискретная математика для программистов. СПб, Питер, 2000.

13. Тишин В.В. Теория алгоритмов, предикаты. Самара, 2001.

14. Фролов И.С. Элементы математической логики. Самара, Самарский университет, 2001.

15. Яблонский С.В. Введение в дискретную математику. М., Высшая школа, 2001.

 

В Содержание.

 

 

Date: 2015-09-24; view: 2388; Нарушение авторских прав; Помощь в написании работы --> СЮДА...



mydocx.ru - 2015-2024 year. (0.007 sec.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав - Пожаловаться на публикацию