Другие неразрешимые проблемы из теории рекурсивных функций

 

· Принадлечит ли произвольное число Y области определения ЧРФ под номером X.

· Проблема определения принадлечит ли функция в ряду ЧРФ под номером X классу общерекурсивных функций.

· Проблема определения, является ли функция под номером X является нуль-функцией.

·

· Проблема определения обладает ли ЧРФ под номером Х произвольным свойством(монотонность, неотрицательность и др.)

 

Различные примечательные неразрешимые проблемы математики

1. Формула в элементарной арифметике состоит из:

Т.е. записи вида:

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

2. Разрешимость логики предикатов первого порядка.

Является ли формула логики предикатов - Е истинной?

3. Проблема сочитаемости Поста

Даны алфавит и множество пар слов в алфавите А. И - множество конечных слов в алфавите А.

PQ называются сочетаемыми если существует такой набор так что

Проблема состоит в том является ли произвольное множество пар слов сочетаемым.

4. Проблема представимости матриц

Представима ли матрица U в базисе

Cущес твует ли такой набор где так чтобы

В этом случае рассматриваются – матрицы и неразрешимость данной проблемы начинается с n=4

5. Проблема тождества элементарных функций вещественного переменного. Т.е. функций:

и функции полученные суперпозицией этих функций.

? – Являются ли функции тождественными

6. Lесятая проблема Гильберта. Проблема разрешимости в целых числах диофантового уравнения.

Задано диофантово уравнение (т.е. уравнение вида: ) с произвольными неизвестными и целыми коэффициентами. Необходимо установить, разрешимо ли уравнение после конечного числа операций в целых числах.

 

Сложность вычислений

Характеристики сложности

Пусть есть машина Тьюринга – Т, которая вычисляет функцию f(x)

Мерой сложности является каличество шагов вычисления.

Определим функцию , равную числу шагов до остановки - n машины Т, выполненному при вычислении f(x), если f(x) определена. Если f(x) не определена, то значение считается неопределенным. Функция называется временной сложностью.

Активной зоной при работе машины Т на слове X называется множество всех ячеек ленты, которые содержат непустые символы, либо посещались в процессе вычисления f(x) головкой машины Т.

Определим функцию , равную длине активной зоны при работе машины Т на слове X, если f(x) определена. Если f(x) не определена, то значение считается неопределенным. Функция называется емкостной(ленточной) сложностью.

Пусть машина Тьюринга Т имеет внешний и внутренний алфавит мощности k и r соответсвенно. Тогда для функций сложности и справедливы оценки:

Покажем это:

В начальный момент на ленте записано слово x длины . На каждом шаге активной становится не более одной новой ячейки, поэтому

Найдём теперь число различных конфигураций с активной зоной . Имеется вариантов записи на ленте, r вариантов выбора положения головки и S вариантов для значения длины конфигурации К. Таким образом, число рассматриваемых конфигураций не превосходит .

Далее, если в процессе работы машины встретятся две одинаковые конфигурации, то машина зациклиться, поскольку конфигурация однозначно определяет следующую за ней. Значит, если машина в процессе вычисления использует зону , то число её шагов не превосходит числа различных конфигураций с зоной не превышающей В итоге получаем неравенство

Вводятся функции временной и емкостной сложности по худшему случаю:

Отметим свойства мер сложностей:

1)

Т.е. области определения совпадают

2) Предикаты вида P(x,y) определенные соотшениями является разрешимым.

Т.е. существует машина Т разрешающая предикаты

В начале на ленте написано слово x, считаем количество шагов y до того как на ленет будет написано f(x): если машина остановится значит y, если не осановится то не y. Таким образом всегда можно сказать, что функция f(x) имеет значение y или не имеет.

Определение абстрактной мерой сложности. Под абстрактной мерой сложности будем понимать любое семейство функций которое обладает свойствами:

1)

2) Преликат – разрешим