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

Доказать, что следующие функции вычислимы

1. ;

2. Усеченная разность

3. ;

4. ;

5. ;

6. ;

7. ;

8. ;

9. ;

10.

11.

12. ;

13. Полиномиальная функция , где ;

14. ;

- наименьшее общее кратное чисел и ;

15. - наибольший общий делитель чисел и ;

16. - число простых делителей числа ;

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

18. ;

19.

20. Докажите следующие свойства усеченной разности

20.1. ;

20.2. ;

20.3. ;

20.4. .

Задание 2

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. Перевести число из пятеричной системы счисления в семеричную.

Задание 3

1. Пусть для слов в алфавите заданы следующие марковские подстановки:

; ; ; ;

; ; ; ;

; ; .

Применить каждую из них к слову .

2. Применить марковские подстановки примера 1 к слову .

3. Применить марковские подстановки из примера 1 к слову .

4. Пусть для слов в алфавите заданы следующие марковские перестановки:

; ; ; ;

; ; ; ;

; ; .

Применить каждую из них к слову максимально возможное число раз.

5. Каждую из марковских подстановок задачи 4 применить к слову максимально возможное число раз.

6. Каждую из марковских подстановок задачи 4 применить к слову максимально возможное число раз.

7. Каждую из марковских подстановок задачи 4 применить к словам из задач 1-3 максимально возможное число раз.

8. Нормальный алгоритм в алфавите задается схемой: , . Применить его к словам:

; ; ; ; ; ; ; ; ; .

Выявить закономерность в работе алгоритма.

9. Сконструировать нормальный алгоритм в алфавите , вычисляющий функцию ;

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

11. Сконструировать нормальные алгоритмы, вычисляющие следующие функции: ; ; ; . Пользуйтесь при этом трехэлементным расширением

основного (цифрового) алфавита .

12. Сконструировать нормальный алгоритм, вычисляющий функцию .

13. Составить нормальный алгоритм в трехэлементном расширении основного алфавита , вычисляющий функцию .

14. Сконструировать нормальный алгоритм в четырехэлементном расширении основного алфавита , вычисляющий функцию .

15. В алфавите , являющемся расширением алфавита , рассмотрим нормальный алгоритм, задаваемый схемой:

.

Применить его к следующим словам и показать, что он вычисляет функцию :

; ; ; .

16. В алфавите , являющемся расширением алфавита , рассмотрим нормальный алгоритм, задаваемый схемой:

.

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

ЗАНЯТИЕ 8. ОБЗОР НЕКЛАССИЧЕСКИХ ЛОГИК

Дата добавления: 2015-06-27