Докажите что график вычислимой тотальной функции разрешим

Разрешимы и неразрешимые множества. График вычислимой функции

Пусть А – подмножество множества натуральных чисел. Характеристической функцией множества А называется функция определяемая условиями

Определение: Множество А называется разрешимым, если его характеристическая функция Х_А вычислима.

Теорема 1. Если А и В – разрешимые множества, то множества разрешимы.

Полухарактеристическая функция множества А:

, такая что

Определение: множество А называется полуразрешимым, если его полухарактеристическая функция вычислима.

Теорема 2.Всякое разрешимое множество полуразрешимо.

Теорема 3.(теорема Поста). Множество разрешимо тогда и только тогда, когда оба множества А и N\A полуразрешимы.

Определение: Множество называется перечислимым, если или А является множеством значений некоторой вычислимой функции.

Теорема 4.Всякое перечислимое множество полуразрешимо.

Теорема 5.(теорема о графике). Частичная функция f из А в В вычислима тогда и только тогда, когда ее график Г_f перечислим.

Формальная теория вычислимости. Исходные функции. Частично рекурсивные функции. Рекурсивные предикаты

Простейшие функции:

Основные вычислительные операторы: оператор суперпозиции частичных функций, оператор примитивной рекурсии.

Примитивно рекурсивные функции. Примеры примитивно рекурсивных функций.

Оператор минимизации. Частично рекурсивные функции. Общерекурсивные функции.

Рекурсивные предикаты. Пусть Р – n- местный предикат на множестве натуральных чисел N. Функция называется характеристической для предиката Р, если эта функция удовлетворяет условиям

Определение: Предикат Р называется рекурсивным (примитивно рекурсивным) если его характеристические функция общерекурсивна( примитивно рекурсивна).

Источник

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки

Правила форума

В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе «Помогите решить/разобраться (М)».

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

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.

Вычислимость и сложность

1) Существует ли алгоритм, проверяющий, работает данная программа полиномиальное время?
Кажется, что нет. Иначе бы без проблем могли установить, как соотносятся классы P и NP.
Но как это доказать?

2) Приведите пример двух непересекающихся неперечислимых множества.
Рассмотрим счётную последовательность всех перечислимых множеств
Может, тогда построим первое неперечислимое множество следующим образом: , а второе , откидывая те числа, которые встречались в

3) (Верещагин, Шень, №13) Покажите, что для всякой вычислимой функции существует вычислимая функция, являющаяся псевдообратной к в следующем смысле: область определения совпадает с областью значений , и при этом для всех , при которых определено.
Мы знаем, что функция вычислима тогда и только тогда, когда её график | f(x)=y\>$» title=»$F = \< | f(x)=y\>$» /> (если определено). Тогда в качестве g можно взять функцию, которая сопоставляет каждому из проекции , такой, что

4) Приведите пример неразрешимого множества , такого, что все его горизонтальные и вертикальные сечения разрешимы.
Ну, может быть, пронумеровать все разрешимые множества составить из них неким способом универсальное и показать, что оно неразрешимо?

5) Докажите, что существует язык, который можно распознать с памятью , но не с памятью
Распознать разрешить? И где можно узнать, что такое «распознать с памятью»?

Заслуженный участник

А почему после выкидывания из элементов останется неперечислимое множество? Вы не доказали.
Почитайте лучше классическую конструкцию рекурсивно неотделимых множеств, в том же Верещагине-Шене.

Верно. Для закрепления можете выразить функцию через с помощью композиции и оператора .

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

Идея в целом понятна, но. Предположим, мы построим такую программу . С учётом построения она точно будет работать неполиномиальное время на входе . Но что это может сказать об исходной ? Или сам «код» должен быть таким, чтобы сразу всё ясно стало?

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

Функция невычислима, поэтому весь график неразрешим. Но разве принадлежность сечению можно будет проверить, если функция невычислима?

Заслуженный участник

Давайте разберем подробнее. Это стандартный прием, Вам его надо понимать.
Мы хотим доказать неразрешимость множества полиномиальных программ, то есть, что не существует вычислимой функции такой, что тогда и только тогда, когда программа имеет полиномиальную асимптотику.
У нас есть набор стандартных неразрешимых задач. У Вас в этом наборе, скорее всего, только пара вариаций проблемы останова, она то нам и нужна. Мы знаем, что не существует вычислимой функции такой, что тогда и только тогда, когда программа останавливается на входе .
Нам надо эти две задачи как-то связать. Как именно? Для того, чтобы доказать, что нельзя вычислить , можно попробовать доказать, что, умея вычислять , мы сумеем вычислить и . Это идея сводимости, помедитируйте над ней немного.
Как мы можем это сделать? Мы можем попробовать определить вычислимую функцию , которая переводит пары, для которых , в программы, для которых и наоборот. Тогда, умея вычислять , мы сможем вычислить и , чего мы сделать никак не можем. Значит, невычислима.

Итак, основная идея. Для того, чтобы доказать, что какая-то функция невычислима, нужно свести к этой функции проблему останова.

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

Какие будут сечения у такого графика?

Последний раз редактировалось alleut 02.10.2012, 18:26, всего редактировалось 1 раз.

1)Если программа работает полиномиальное время, то она должна за полиномиальное время выдавать результат для любого входа, в т. ч. для своего номера.
Получается, такая программа должна останавливаться на своём входе, и для полиномиальных алгоритмов мы можем решить проблему остановки.
Как-то так?

Или набор значений, соответствующих одному аргументу,
или набор аргументов, соответствующих одному значению.

Заслуженный участник

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

Угу. И будут ли эти множества разрешимыми?

?

Заслуженный участник

Ну пусть — это неполиномиальная программа, реализующая тотальную функцию. Подходит ли Ваша функция под условие «, которая переводит пары, для которых , в программы, для которых и наоборот.»?

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей

Источник

Вычислимость, разрешимость и перечислимость

Вычислимые функции

Несколько замечаний по поводу этого определения:

Входами и выходами алгоритмов могут быть не только натуральные числа, но и двоичные строки (слова в алфавите <0,1>), пары натуральных чисел, конечные последовательности слов и вообще любые, как говорят, » конструктивные объекты «. Поэтому аналогичным образом можно определить понятие, скажем, вычислимой функции с двумя натуральными аргументами, значениями которой являются рациональные числа.

Несколько десятилетий назад понятие алгоритма требовало специального разъяснения. Сейчас (» компьютерная грамотность «?) такие объяснения все равно никто читать не будет, поскольку и так ясно, что такое алгоритм. Но все же надо соблюдать осторожность, чтобы не принять за алгоритм то, что им не является. Вот пример неверного рассуждения:

Разрешимые множества

Другими словами, X разрешимо, если его характеристическая функция вычислима.

Аналогично определяют разрешимость множеств пар натуральных чисел, множеств рациональных чисел и т.п.

Перечислимые множества

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

Чтобы доказать эквивалентность этих определений, воспользуемся возможностью пошагового исполнения алгоритма.

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

Теорема 1. Пересечение и объединение перечислимых множеств перечислимы.

4. Проведите это рассуждение, используя какое-либо другое эквивалентное определение перечислимости.

Как мы увидим, дополнение перечислимого множества не обязано быть перечислимым.

5. Иногда говорят о так называемых » недетерминированных алгоритмах » (оксюморон, но распространенный) такой алгоритм включает в себя команды типа

(достаточно, впрочем, команды » n := 0 или 1 «, так как произвольное число можно формировать по битам). Недетерминированный алгоритм (при одном и том же входе) может действовать по-разному, в зависимости от того, какие » произвольные » числа будут выбраны. Докажите, что перечислимое множество можно эквивалентно определить как множество чисел, которые могут появиться на выходе недетерминированного алгоритма (при фиксированном входе).

6. Докажите, что если множества и перечислимы, то их декартово произведение также перечислимо.

Источник

Лекция 3. Вычислимые функции

Теория вычислимых функции разрабатывалась А. Чёрчем, и целью ее построения являлось получение точного (формального) определения понятия «алгоритм».

Для того, чтобы дать точное понятие алгоритма, необходимо определить, как задаются данные, с которыми будет работать Исполнитель, и как задаются элементарные шаги, из которых состоит алгоритм.

Универсальный способ представления различных данных – это представление их словами в некотором конечном алфавите. Действительно:

· если объект число, его можно представить в десятичной или двоичной форме, т. е. цепочкой символов алфавита <0,1>, или алфавита <0..9>.

· если объект – программа, то она является цепочкой символов в алфавите, содержащем буквы, цифры и специальные символы.

· если объект – изображение, то он представляется массивом пикселов, а каждый пиксел – тремя числами (интенсивностями красного, зеленого и синего цветов), т. е. изображение так же может быть закодировано строкой символов.

· современные высококачественные системы цифровой записи звука показывают, что и этот объект может быть адекватно описан строкой символов.

Таким образом, можно считать, что алгоритм – это преобразование слов из заданного алфавита в результирующее слово. Каким бы ни был конечный алфавит, любой его символ может быть закодирован с помощью двоичного алфавита. Иначе говоря, входные данные алгоритма могут быть представлены конечной цепочкой битов. То же самое можно сказать и о выходных данных. Каждая цепочка битов может интерпретироваться как целое неотрицательное число. Из этого можно сделать важный вывод: любому алгоритму может быть поставлена в соответствие некоторая функция, отображающая множество неотрицательных целых чисел в себя. Однако мы не утверждаем обратного. Существуют функции, не вычисляемые ни каким алгоритмом.

Вычислимой называют функцию, вычисляемую некоторым алгоритмом.

Вычислимая функция определяется на множестве целых неотрицательных чисел, результат функции так же должен принадлежать множеству целых неотрицательных чисел.

Итак, вычислимая функция – функция, для которой можно построить некоторый алгоритм. Алгоритм дает процедуру отыскания значений вычислимой функции. Но как отличить вычислимую функцию от невычислимой? Можно ли традиционным математическим языком описать общий вид вычислимых функций? А, написав, навести некоторый порядок среди алгоритмов, точнее ввести некий канонический вид написания алгоритмов, соответствующий строению вычислимых функций (мы помним, что для одной функции можно написать бесконечно много эквивалентных алгоритмов).

Для того чтобы внести ясность в эту проблему, поступим следующим образом.

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

2. Введем операции над функциями. Операции получают сами функции (а не значения функций) в качестве операндов и дают в результате новые функции. Эти операции так же должны быть очевидны с математической точки зрения, т. е. не должно возникать сомнений в том, что из вычислимых функций с помощью этих операций получаются вновь вычислимые функции. Обозначим набор этих операций О.

3. Произведем (мысленно) все возможные операции набора О над базовыми функциями набора Р, при этом будем по-разному комбинировать их в качестве аргументов. Все новые полученные функции включим в набор P и вновь произведем все возможные операции из набора О, подставляя в виде аргументов и по-разному комбинируя все возможные функции из уже расширенного набора P. Полученные при этом новые функции, так же включим в P и т. д.

При этом мы не ограничиваем сверху количество исполнений п.3., то таким образом будем получать все новые и новые функции. Иначе говоря, пп.1-3 описывают построение некоторого бесконечного множества функций. Однако, необходимо отметить, что каждая конкретная функция f из этого множества является результатом выполнения конечного числа операций, взятых из набора О над базовыми функциями.

Таким образом, процесс построения одной конкретной функции f:

1) начинается с исходных данных, выбираемых из базового набора;

2) выполняется пошагово (в дискретном времени);

3) на каждом шаге выполняется одна из элементарных операций (из набора О);

4) результат каждого шага строго определен;

5) процесс заканчивается через конечное число шагов.

Этот перечень дает нам возможность говорить об алгоритме αf построения функции f.

Заметим, что мы не вносим саму функцию f в перечень исходных данных, т. е. не говорим об универсальном алгоритме построения функции. Напротив, для различных функций f1 и f2 алгоритмы будут различны. Более того, свойство массовости алгоритмов не выполняется, т. к. исходные данные всегда одни и те же – базовый набор функций. Это позволяет говорить о том, что текст алгоритма (последовательность применения операций из О и места подстановок в эти операции операндов из базового набора) задает единственную функцию, а не множество функций. Таким образом, универсальный алгоритм, который на основе базовой функции построил бы любую функцию не существует.

С другой стороны, легко преобразовать алгоритм αf построения функции в алгоритм вычисления значений функции f(x1,x2,…,xn) введением и использованием в тексте исходных данных x1,x2,…,xn.

Введем сейчас конкретные базовый набор функций P и систему операций О для формирования множества функций. В качестве области определения функций возьмем n-кратное декартово произведение множества неотрицательных целых чисел. Сами функции, как и их аргументы также принимают значения из множества неотрицательных целых чисел. Таким образом, мы обеспечиваем возможность, хотя бы потенциальную, вычислять значения функций, с помощью рассмотренных ранее машин Тьюринга.

Базовый набор функций.

P=<Z(x), S(x), >

Z(x)=0, S(x) = x+1, =xm

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

1. Вычисление функции S(x)=x+1, увеличение аргумента на единицу. Используем алфавит A*=<0, 1, e>, причем x, будем кодировать последовательностью нулей и единиц, так как это принято в двоичном кодировании целых неотрицательных чисел. В момент старта головка машины Тьюринга находится напротив крайней левой ячейки с символом 1. В момент окончания работы головка машины Тьюринга так же должна находиться в крайнем левом положении (напротив крайней левой ячейки с символовом 1).

Источник