10.Другие примеры неразрешимых алгоритмически задач
Рассмотрим уравнение fy(x) = с, где c – положительное целое число, например
2*x=4. Здесь fy(x) =2*x. Обратная функция есть x=0.5*y. Найти корень уравнения 2*x=4 это то же самое, что ответить на вопрос: останавливается ли на входе y=4 машина, вычисляющая обратную функцию. Таким образом, проблема отыскания корня произвольной вычислимой функции на произвольном входе равносильна проблеме останова, а последняя алгоритмически не разрешима.
11.Методы задания машин Тьюринга
Первый язык программирования создала соратница Ч. Бэббеджа Ада Ловлейс (дочь великого английского поэта Байрона). В языке А. Ловлейс были три оператора:
присвоить (=)
проверить условие (Если … То …)
перейти (goto …)
Наша задача состоит в том, чтобы показать, что с помощью этих операторов можно запрограммировать любой алгоритм (любую вычислимую функцию). Для этого надо просто показать, как реализовать программно правила машины Тьюринга.
Рассмотрим правило
Qj Qi R.
Его программная реализация такова:
again:
прочитать_символ(X);
Если (X=) & (Состояние=Qj) То
{
Cостояние= Qi
записать_символ ()
перейти_к_следующей_ячейке
goto again
}
Else
//Делать обработку других правил
12.Граф-схемы и их связь диаграммой состояний автоматов.
Графом называется множество вершин и связывающих их ребер. Пример графа дает рис.1.
Вершины представлены с помощью кружков. Номера вершин указаны числами внутри кружков. Ребра – отрезки прямых линий, соединяющие вершины.
Будем говорить, что вершина i покрывает некоторое ребро, если данная вершина i является концевой вершиной рассматриваемого ребра.
Множество вершин называется вершинным покрытием, если для каждого ребра графа найдется хотя бы одна вершина из , которая ее покрывает. Так, одним из возможных вершинных покрытий представленного выше графа, является ={2,4,5}.
Задача ВЕРШИННОЕ ПОКРЫТИЕ требует найти покрытие с заданным числом вершин.
13.Рекурсивные функции и их построение из простейших + (кратко рассказать 14 вопрос)
Некоторые функции объявляются первичными. Первичную функцию нельзя заменить вычислением более простых функций. Из этих первичных функций строится с помощью определенных операций все множество известных нам вычислимых функций. Таких первичных функций над целыми положительными числами всего три.
А).
Функция
константа
Б)
Функция
непосредственного следования
В)
Тождественная
функция
14 .Операторы подстановки, рекурсии и минимизации. Частично рекурсивные функции
Для построения более сложных функций из первичных используют следующие операции.
Операция подстановки. Эта операция заключается в том, что вместо каких-то переменных функции подставляют другие функции от тех же или иных переменных.
Пример.
Пусть
и
.
Тогда подставив вместо переменной х
функцию g(у),
получим новую функцию:
Операция примитивной рекурсии. Эту операцию можно представить следующим образом
Пример
1. Пусть
- известная вычислимая функция, т.е.
известен алгоритм вычисления этой
функции для произвольного х. Определим
новую функцию f(x)
следующим образом:
Это и есть определение функции с помощью операции примитивной рекурсии.
Например,
пусть
Это есть определение целочисленного умножения. Так
f(3,3)=f(3,2)+3=f(3,1)+3+3=3+3+3=9.
Пример
2.
и
Это
определение позволяет находить значение
.
В самом деле, рассмотрим следующий
пример вычисления 32
.
f(3,1+1)=h(3,f(3,1))=h(3,3)=h(2+1,3)=h(2,3)+3=h(1+1,3)+3=h(1,3)+3+3=3+3+3=9
Определение. Функция, определяемая из простейших с помощью операций подстановки и/или примитивной рекурсии, называется примитивно рекурсивной.
Имеется еще одна операция для построения рекурсивных функций. Правда, эта операция не всегда дает результат или, как говорят, не является полностью определенной (тотальной). Эта операция называется операцией минимизации (взятия минимального корня). Ее определение таково.
Эту операции можно для простоты обозначить как y f(x,y).
Пример
3. Пусть
.
Тогда y
f(3,y)=2.
Определение. Функция, определяемая из простейших с помощью операций подстановки примитивной рекурсии и минимизации, называется частично рекурсивной.