Контрольная работа по предмету «Теория алгоритмов» Вариант 3 Тишин

Решить задачи № 3.1.3, 3.1.4, 3.2.3, 3.3.1, 4.1.4, 4.1.5, 4.1.6. из Учебника В.В. Тишина
"Дискретная математика в примерах и задачах".

В табл.3.1.3 и везде далее наш 3-й вариант, т.е. строка под №3

Задание 3.1.3
1. Написать формулу числовой функции f(x1, x2, …, xn), вычислимой машиной Тьюринга с множеством внутренних состояний {0, 1, 2, 3, 4, 5, 6}, где 0 – заключительное, а 1 – начальные состояния, если машина задана своей программой.
2. Проверить работу машины Тьюринга с некоторым набором значений аргументов.
Решение

Задание 3.1.4
1. По данному коду N(T) восстановить программу машины Тьюринга.
2. Выяснить, является ли машина Е самоприменимой или несамоприменимой.
При составлении N(T) использована следующая кодировка:
П – 1, Л – 12, Н – 13, λ – 14, 1 – 15, * – 16, s0 – 17, ...

Задание 3.1.3 3
Задание 3.1.4 4
Задание 3.2.3 5
Задание 3.3.1 6
Задание 4.1.4 7
Задание 4.1.5 8
Задание 4.1.6 8
Список использованных источников 10

-

1А, λ*Аs1 s0Как видим, при работе над своим кодом машина Тьюринга перешла в своё заключительное состояние, значит, она является самоприменимой.Задание 3.2.31. Написать формулу для функции y=f(x1, x2, …, xn), вычисляемой нормальным алгоритмом.2. Проверить работу алгоритма над некоторым набором значений аргументов.n=21*1→**1**→****→.1111Решение1. Вначале мы имеем запись изображения набора аргументов 1x+1*1y+1. Запишем последовательность слов, получающихся при работе данного нормального алгоритма над словом 1x+1*1y+1:1x1*11y, 1x-11**1y, 1x-21**1y, …, **1y, 1y+4.fx,y=y+32. Проверим работу алгоритма над изображение набора аргументов (1, 0): 11*1, 1**, **, 1111.И над изображение набора аргументов (0, 2): 1*111, **11, 111111.Видим, что f(1, 0)=0+3=3, f(0, 2)=2+3=5, что и планировалось получить.Задание 3.3.1Найти функцию f(x, y), полученную из функций g(x) и h(x, y, z) по схеме примитивной рекурсии.g(x)=xh(x, y, z)=x+y-zРешениеНайдём несколько значений функции f:f(x,0)=g(x)=x;f(x,1)=h(x,0,f(x,0))=h(x,0,x)=x+0-x=0;f(x,2)=h(x,1,f(x,1))=h(x,1,0)=x+1-0=x+1;f(x,3)=h(x,2,f(x,2))=h(x,2,x+1)=x+2-(x+1)=1;f(x,4)=h(x,3,f(x,3))=h(x,3,1)=x+3-1=x+2;f(x,5)=h(x,4,f(x,4))=h(x,4,x+2)=x+4-(x+2)=2;f(x,6)=h(x,5,f(x,5))=h(x,5,2)=x+5-2=x+3;f(x,7)=h(x,6,f(x,6))=h(x,6,x+3)=x+6-(x+3)=3;Возникает предположение, что f(x,y)={(y+1)/2}•2•x+[y/2]. Докажем это методом математической индукции, проведя индукцию по y::1) Проверка при y=0.f(x,0)=x={(0+1)/2}•2•x+[0/2];2) Допустим, что предположение верно при y=n, то есть верна формула f(x,n)={(n+1)/2}•2•x+[n/2];3) Докажем, что предположение верно и при y=n+1, то есть докажем справедливость формулы f(x,n+1)={((n+1)+1)/2}•2•x+[(n+1)/2]f(x,n+1) = h(x,n,f(x,n)) = h(x,n,{n/2}•x+[n/2]) = x+n-({(n+1)/2}•2•x+[n/2]) = x+n-{(n+1)/2}•2•x-[n/2] = (1-{(n+1)/2}•2)•x+(n-[n/2]) = {((n+1)+1)/2}•2•x+[(n+1)/2]На основании метода математической индукции утверждаем, что предположение справедливо для всех yϵN0.Ответ: f(x,n)={(n+1)/2}•2•x+[n/2].Задание 4.1.4Предикаты P и Q определены на множестве {a,b,c}.1. Найти предикат, равносильный предикату R, но не содержащий кванторов.2. Выяснить, может ли предикат R быть выполнимым, но не тождественно истинным.zyP(y,z)xQ(x,y)Решение1. zyP(y,z)xQ(x,y) = ( yP(y,a) ˅ yP(y,b) ˅ yP(y,c) ) Q(а,y)Q(b,y)Q(c,y) = ( (P(a,a)P(b,a)P(c,a)) ˅ (P(a,b)P(b,b)P(c,b)) ˅ (P(a,c)P(b,c)P(c,c)) ) Q(а,y)Q(b,y)Q(c,y)2. Пусть P(y,z) – тождественно истинный предикат. Тогда высказывание (P(a,a)P(b,a)P(c,a)) ˅ (P(a,b)P(b,b)P(c,b)) ˅ (P(a,c)P(b,c)P(c,c)) истинно, а выражение zyP(y,z)xQ(x,y) равносильно выражению Q(а,y)Q(b,y)Q(c,y).Если положить Q(a,a)=Q(b,a)=Q(c,a)=1, Q(a,b)=0, то R(a)=1111=1; R(b)=10…=0.Итак, предикат R(y) может быть выполнимым, но не тождественно истинным.Задание 4.1.51. Представить в приведённой форме предикат D варианта №.(xyT(x,y)→R(x,z))|xP(x,y)2. Представить в предварённой нормальной форме предикат D варианта №+1.(xyP(y,z,t)|R(x,y,z))yT(x,y,t)Решение1.