Разработать тьюринговые функциональные схемы для решения следующих задач

1. Сложение двух чисел в бинарной системе счисления.

2. Перевод числа из двоичной системы счисления в унарную и наоборот.

3. Умножение двух чисел в унарной системе счисления.

4. Найти функцию если и если .

5. Проверить на четность число, записанное в двоичной системе счисления.

6. Перевод числа из пятеричной системы счисления в семеричную.

7. Дано число в унарной системе счисления. Определить, делится ли оно на 3?

8. Даны два числа. Определить, какое из них больше? Алфавит любой.

9. Перевод числа из унарной системы счисления в десятичную систему счисления.

10. Вычисление модуля разности двух чисел, записанных в унарной системе счисления.

11. Произведение двух чисел в унарной системе счисления.

12. Перевод десятичного числа в унарную систему счисления.

13. Перевод числа из унарной системы счисления в бинарную.

14. Найти остаток от деления унарного числа на 2.

15. Извлечение целой части квадратного корня в унарной системе счисления.

16. Произведение двух чисел в бинарной системе счисления.

17. Распознать язык Дика – скобочные скелеты арифметических выражений. Примеры цепочек такого языка “(( ))”; “(( )) ((( ) ( )))”.

18. Распознать язык . Примеры цепочек этого

 

языка “ ”, “ ” (воспользоваться соотношением или тем, квадрат натурального числа представим как сумма последовательных нечетных чисел).

19. Распознать язык, цепочки которого содержат одинаковые количества вхождений символов . Пример цепочки такого языка ” ”.

20. Увеличить на один двоичные числа и уменьшающие на один двоичные числа.

21. Удвоить натуральные числа, записанные в унарной системе счисления.

22. Перевести число из унарной системы в троичную.

23. Распознать четность натурального числа.

24. Найти остаток от деления натурального числа на .

25. Вычислить следующие функции, заданные на

25.1. ; 25.2. ; 25.3. ;

25.4. .

26. Вычислить следующие функции, определенные на .

26.1. ; 26.2. ;

27. Найти остаток от деления десятичного числа на 3.

28. Найти разность двух чисел, записанных в троичной системе счисления.

29. Дано два числа в унарной системе счисления. Разработать алгоритм, который бы обеспечивал бесконечный процесс прибавления левого числа к правому, затем левого числа к полученной сумме и так далее.

30. Реализовать алгоритм Евклида для нахождения НОД двух чисел, представленных в унарной системе счисления.

31. На ленте записаны два унарных числа, разделенных между собой звездочкой. Сохранить большее из заданных чисел, а меньшее стереть.

 

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

которая строит массив, равный данному и отстоящий от него вправо на две неотмеченные ячейки.

33. Дан массив, длина которого выражается нечетным числом. Найти середину массива, то есть стереть метку в секции, которая делит массив на две равные части.

34. Пусть на ленте машины Тьюринга помещена последовательность чередующихся между собой символов “ ” и “ ”. Необходимо составить программу, работая по которой, машина уничтожит символы “ ”, а “ ” расположить рядом

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

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

37. На ленте записано слово в алфавите . Верно ли, что все буквы слова одинаковы?

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

39. Дано два числа в унарной системе счисления. Представить их наибольший делитель в десятичной системе счисления.

 

40. Реализовать функцию .

41. Реализовать функцию .

42. Найти сумму двух чисел, заданных в бинарной системе счисления.

43. Реализовать целочисленное деление десятичного числа на 3.

44. Перевести число из пятеричной системы счисления в семеричную.

 

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

 

1.Лихтарников Л.М. Математическая логика и теория алгоритмов / Л.М. Лихтарников. Т.Г., Сукачева. М.: Факториал, 2000. 420 с.

2. Метакидес Г. Принципы логики и логического программирования / Г. Метакидес, А. Нероуд. М.: Факториал. 1998. 450 с.

3. Карпов Ю.Г. Теория автоматов / Ю.Г. Карпов. М.: Питер.2002. 435 с.

4. Холопкина Л.В. Математическая логика и теория алгоритмов: учеб. пособие для вузов / Л.В. Холопкина. Воронеж: ВГТУ, 2008. 162 с.

 

СОДЕРЖАНИЕ

 

Лабораторная работа № 4. Исчисление предикатов 1

1. Цель работы 1

2. Краткие теоретические сведения 1

2.1. Кванторные операции 2

2.2. Равносильности логики предикатов 5

2.3. Предваренная, сколемовская нормальная

и сколемовская стандартная формы 6

3. Контрольные вопросы и задания 8

 

Лабораторная работа № 5. Перевод высказываний естественного языка на язык исчисления предикатов 14

1. Цель работы 14

2. Краткие теоретические сведения 14

3. Контрольные вопросы и задания 16

Лабораторная работа № 6. Логический 21

вывод в исчислении предикатов

1. Цель работы 21

2. Краткие теоретические сведения 21

2.1.Метод семантических таблиц 21

2.2. Принцип резолюции 24

2.2.1. Алгоритм унификации 24

2.2.2. Метод резолюций в исчислении 31

предикатов

3. Контрольные вопросы и задания 35

Лабораторная работа № 7. Теория алгоритмов 38

1. Цель работы 38

2. Краткие теоретические сведения 39

2.1. Вычислимые функции, частично- рекурсив-

ные и общерекурсивные функции. Тезис Черча 39

2.2. Машинная математика. Машина Тьюринга 44

2.3. Тезис Тьюринга 48

3. Контрольные вопросы и задания 48

Библиографический список 53

 

 

Методические указания

к выполнению лабораторных работ 4-7 по дисциплине

“Математическая логика и теория алгоритмов”

для студентов специальности 230101

очной, сокращенной очной, заочной и сокращенной заочной форм обучения

 

 

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

Холопкина Людмила Владимировна

Носачева Майя Павловна

 

 

В авторской редакции

 

 

Подписано в печать 18.03.09.

Формат 60х84/16. Бумага для множительных аппаратов.

Усл. печ. л. 3,5. Уч.- изд.л. 3,3. Тираж 150 экз.”C”.

Зак. №

 

ГОУВПО «Воронежский государственный

технический университет»

394026 Воронеж, Московский просп., 14