Ошибки в теории вычислимости

[Андрей АK]

1) Утверждение, что множество всех алгоритмов - перечислимое множество - неверно!
Проведем аналогию с множеством действительных чисел.
Если допускается существование множества чисел, с бесконечным рядом десятичных знаков (действительных), то должны существовать и алгоритмы с бесконечным количеством команд.

Назовем такие алгоритмы - бесконечными - т.е. это не те, которые никогда не заканчиваются, а те, у которых бесконечное число команд.

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

Итак перечислимо только множество конечных алгоритмов.

Теперь, следствие.
К чему привело неправильное положение о перечислимости множества всех алгоритмов:

2) Ошибочна оказалась теорема о существовании невычислимых функций.
В частности, следующее её доказательство:

Цитата:

Пронумеруем все (!только конечные) алгоритмы.
В результате, каждый получит свой номер $k$. Алгоритм обозначим $P_{k}$ а сответствующую функцию через $f_{k}(n)$
Рассмотрим теперь функцию.
$h(n)= \{\ f_{n}(n) + 1$-если $f_{n}(n)$ определено, $0$ если нет $\}\
Она невычислима.
Доказательство - от противного.
Положим $h(n)= f_{p}(n)$ при некотором $p$.
Но этого не может быть, так как $h(p)<> f_{p}(p)$ , если значение $f_{p}(p)$ определено и $h(p)$ определено, если $f_{p}(p)$ неопределено.

Однако, в этом доказательстве делается грубая ошибка - предполагается, что функция $h(n)$ реализуется конечным алгоритмом, тогда как, поскольку эта функция "знает" все номера , всех на свете конечных алгоритмов , то такая функция должна реализоваться исключительно бесконечным алгоритмом и её номера среди списка всех конечных алгоритмов,естественно, нет. (Числа $p$ не существует)

Доказательство ошибочно.

Если есть другое, то можно его рассмотреть, но я такого пока не нашёл.

[Xaositect]

Андрей АK в сообщении #286781 писал(а):

Назовем такие алгоритмы - бесконечными - т.е. это не те, которые никогда не заканчиваются, а те, у которых бесконечное число команд.

Определение алгоритма, пожалуйста.

Андрей АK в сообщении #286781 писал(а):

Если есть другое, то можно его рассмотреть, но я такого пока не нашёл.

Если вы корректно введете свои бесконечные алгоритмы, то, может быть, и приведу доказательство либо соглашусь, что все функции "вычислимы по Андрею АК".
Вполне возможно, что то, что Вы сформулируете, будет равномощно $\Delta^0_2$, $\Delta^0_\omega$, или еще чему-нибудь очень сильному, но все же не вычисляющему все.

Теория вычислимости в основном имеет дело с б.-м. четко очерченным кругом моделей вычисления, равномощных машинам Тьюринга, или более слабым (я сейчас не говорю про модели с оракулами и иерархии неразрешимости). В математической теории алгоритм - синоним машины Тьюринга - Вы, видимо, называете их "конечными алгоритмами".
Есть еще философская составляющая (тезис Черча) - считается, что любое "механическое" вычисление может быть представлено в виде МТ. Но это вопрос не математики, а философии математики.

[vek88]

Андрей АK в сообщении #286781 писал(а):

1) Утверждение, что множество всех алгоритмов - перечислимое множество - неверно!

Батенька! Это строго доказанная - и доказанная в высшей степени конструктивно - Теорема. В качестве простейшего для Вашего понимания доказательства рекомендую Мартин-Леф "Очерки по конструктивной математике", Глава 1, раздел 7 "Универсальная система". Там построена каноническая система, описывающая все РП-множества (что эквивалентно всем алгоритмам) в заданном алфавите.

А также в качестве домашнего задания предлагаю Вам доказать следующее утверждение.

Теорема. Если у кого-то где-то множество всех алгоритмов не является рекурсивно перечислимым множеством, то значит этот кто-то не знает что такое алгоритм.

К сказанному уважаемым Xaositect добавлю, что вместо алгоритма можно, при необходимости, использовать более "мощные" понятия. Я, например, большой энтузазист К-систем/полных К-систем (они эквивалентны $\Pi^1_1$/$\Delta_1^1$-множествам). Но это уже другая история, не относящаяся к традиционному понятию вычислимости и/или РП-перечислимости.

[Андрей АK]

Xaositect в сообщении #286785 писал(а):

Если вы корректно введете свои бесконечные алгоритмы, то, может быть, и приведу доказательство либо соглашусь, что все функции "вычислимы по Андрею АК".

Незачем далеко ходить.
Возьмем цитаты из Википедии:
1) «Алгоритм — это конечный набор правил, который определяет последовательность операций для решения конкретного множества задач и обладает пятью важными чертами: конечность, определённость, ввод, вывод, эффективность». (Д. Э. Кнут)
Ключевое слово здесь - "конечный".
Т.е. конечность алгоритмов - здесь никакая не теорема, а просто определение.
Т.е. достаточно убрать это слово и получим "определение алгоритма «по Андрею AK»"
2)«Алгоритм — это всякая система вычислений, выполняемых по строго определённым правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи». (А. Колмогоров)
Здесь нет никакого ограничения на количество правил, следовательно это определение включает в себя и бесконечные алгоритмы.
Дальше можно не цитировать.
Одни определения алгоритмов относятся к "конечным алгоритмам", другие - "к действительным" (в т .ч . к бесконечным).
Я бы не стал возражать против того, что современная теория алгоритмов изучает только "конечные алгоритмы" ... но поскольку "в доказательстве невычислимости" ,что я привел, идет путаница - бесконечный алгоритм объявляется конечным, то приходится признать, что алгоритмы (например, по Колмогорову) - могут быть как конечными, так и бесконечными.
К стати - смешно - но по Колмогорову не существует невычислимых алгоритмов, поскольку таково его определение: "после какого-либо числа шагов заведомо приводит к решению поставленной задачи".
Т.е. ,по Колмогорову, невычислимый алгоритм - это не алгоритм.

-- Ср фев 10, 2010 00:45:47 --

vek88 в сообщении #286800 писал(а):

Батенька! Это строго доказанная - и доказанная в высшей степени конструктивно - Теорема.

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

[Xaositect]

Мы, кажется, говорим о математической теории?
Следует четко разделять неформальное понятие алгоритма, определения которого вы даете, от формализованного понятия алгоритма, задаваемого определением машины Тьюринга, либо нормального алгоритма, либо лямбда-исчисления, либо системы равенств, либо машины Колмогорова-Шёнхаге...
Дайте формальное определение.

-- Ср фев 10, 2010 00:07:15 --

Андрей АK в сообщении #286813 писал(а):

Я бы не стал возражать против того, что современная теория алгоритмов изучает только "конечные алгоритмы" ... но поскольку "в доказательстве невычислимости" ,что я привел, идет путаница - бесконечный алгоритм объявляется конечным, то приходится признать, что алгоритмы (например, по Колмогорову) - могут быть как конечными, так и бесконечными.

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

[Maslov]

Андрей АK в сообщении #286813 писал(а):

2)«Алгоритм — это всякая система вычислений, выполняемых по строго определённым правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи». (А. Колмогоров)
Здесь нет никакого ограничения на количество правил, следовательно это определение включает в себя и бесконечные алгоритмы.

Это Вы где такое определение у Колмогорова нашли?

В книге Колмогоров А.Н. — Теория информации и теория алгоритмов на стр. 24 написано буквально следующее:

Цитата:

Мы отправляемся от следующих наглядных представлнений об алгоритмах:

1) Алгоритм $\mathrm{\Gamma}$, применённый ко всякому "условию"("начальному состоянию") $A$ из некоторого множества $\mathfrak{G} (\matrm{\Gamma})$ ("области применимости" алгоритма $\Gamma$), даёт "решение" ("заключительное состояние") $B$.

2) Алгоритмический процесс расчленяется на отдельные шаги заранее ограниченной сложности; каждый шаг состоит в "непосредственной переработке" возникшего к этому шагу состояния $S$ в состояние $S^* = \Omega_{\Gamma}(S)$

3) Процесс переработки $A^0 = A$ в $A^1 = \Omega_{\Gamma}(A^0)$, $A^1$ в $A^2 = \Omega_{\Gamma}(A^1), A^2$ в $A^3 = \Omega_{\Gamma}(A^2)$ и т. д. продолжается до тех пор, пока либо не произойдёт безрезультатная остановка (если оператор $\Omega_{\Gamma}$ не определен для получившегося состояния), либо не появится сигнал о получении "решения". При этом не исключается возможность неограниченного продолжения процесса (если никогда не появится сигнал о решении).

4) Непосредственная переработка $S$ в $S^* = \Omega_{\Gamma}(S)$ производится лишь на основании информации о виде заранее ограниченной "активной части" состояния $S$ и затрагивает лишь эту активную часть.

Предполагается строгое определение, отображающее эти наглядные представления в точных математических терминах.

Состояния изображаются топологическими комплексами специального вида. Активная часть состояния образуется из всех элементов комплекса, удаленных на расстояние не более заданного от некоторой начальной вершины. Оператор $\Omega_{\Gamma}$ задается конечным набором правил. Каждое из этих правил имеет вид $U_i \to W_i$; его применение состоит в том, что если активная часть комплекса $S$ есть $U_i$, то, чтобы получить $S^* = \Omega_{\Gamma}(S)$, следует $U_i$ заменить на $W_i$, оставив неизменным $S \setminus U_i$.

[Андрей АK]

Xaositect в сообщении #286820 писал(а):

Мы, кажется, говорим о математической теории?
Следует четко разделять неформальное понятие алгоритма, определения которого вы даете, от формализованного понятия алгоритма, задаваемого определением машины Тьюринга, либо нормального алгоритма, либо лямбда-исчисления, либо системы равенств, либо машины Колмогорова-Шёнхаге...
Дайте формальное определение.

Я что монографию тут написать должен?
Хорошо, вот определение, которое мне нравится:
Алгоритм - это иерархический граф в узлах которого расположены конечные или счетные наборы полиномов, от конечного или счетного количества переменных, с конечным или счетным количеством мономов.
В полиномах используются только операции сложения и умножения.
Правила сложения и умножения - определяется языком, но обладают свойствами кольца.
Вычисление алгоритма - это последовательное вычисление полиномов, начиная с корневого узла и далее по некоему пути в графе, определяемому значениями некоторых переменных, отвечающих за направление вычислений (можно называть их временными переменными).
Другой набор переменных отвечает за результат вычислений (можно называть их пространственными переменными).
Вычисление алгоритма прекращается по достижении тупиковой ветви графа.
В узлах графа реализуются "параллельные вычисления" - все ,находящиеся там, полиномы вычисляются одновременно и результат их вычислений не зависит от хода вычислений других полиномов ,того-же узла.

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

Xaositect в сообщении #286820 писал(а):

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

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

-- Ср фев 10, 2010 01:53:33 --

Maslov в сообщении #286823 писал(а):

Это Вы где такое определение у Колмогорова нашли?

Вы внимательно читали?
Я же написал где - в Википедии, ищите ссылку на слово "Алгоритм".

[Xaositect]

Андрей АK в сообщении #286825 писал(а):

Алгоритм - это иерархический граф в узлах которого расположены конечные или счетные наборы полиномов, от конечного или счетного количества переменных, с конечным или счетным количеством мономов.
В полиномах используются только операции сложения и умножения.
Правила сложения и умножения - определяется языком, но обладают свойствами кольца.
Вычисление алгоритма - это последовательное вычисление полиномов, начиная с корневого узла и далее по некоему пути в графе, определяемому значениями некоторых переменных, отвечающих за направление вычислений (можно называть их временными переменными).
Другой набор переменных отвечает за результат вычислений (можно называть их пространственными переменными).
Вычисление алгоритма прекращается по достижении тупиковой ветви графа.
В узлах графа реализуются "параллельные вычисления" - все ,находящиеся там, полиномы вычисляются одновременно и результат их вычислений не зависит от хода вычислений других полиномов ,того-же узла.

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

-- Ср фев 10, 2010 01:11:32 --

Да, кстати, многочлены со счетным числом мономов создают некоторые проблемы - их значение может быть неопределенным. Впрочем, это ладно, это можно учесть.

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

[Андрей АK]

Xaositect в сообщении #286828 писал(а):

Под иерархическим графом Вы понимаете ориентированный граф без циклов или что?

Это я ещё не уверен.
Вроде бы, любой алгоритм можно свести к графу без циклов.
Но тогда (если не будет циклов) в моё определение не попадут рекурсивные функции, а этого не хотелось бы.
Значит оставляем циклы.
Ещё ,наверное, можно ввести несколько операций сложения и умножения - чтоб расширить определение алгоритма до избыточных алгоритмов (это например, если я в булевых функциях буду использовать более чем полную систему функций).

-- Ср фев 10, 2010 02:21:11 --

Xaositect в сообщении #286828 писал(а):

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

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

[Xaositect]

Ну да ладно.
С тем, что таких "бесконечных алгоритмов" счетное число, Вы согласны?

-- Ср фев 10, 2010 01:24:16 --

Андрей АK в сообщении #286830 писал(а):

Их несчетность доказывается способом, аналогичным доказательству несчетности действительных чисел.

А, стоп, действительно, я неправ.

[Андрей АK]

Xaositect в сообщении #286831 писал(а):

Ну да ладно.
С тем, что таких "бесконечных алгоритмов" счетное число, Вы согласны?

Нет, уже успел ответить.
Подобно несчетности действительных чисел - количество бесконечных алгоритмов тоже несчетно.

[Xaositect]

Ну хорошо.
Любая функция вычислима с помощью "бесконечного алгоритма". Потому что она представляется в виде $f(x) = \sum_{i\in\mathbb{N}} I_i(x)f(i)$, где $I_i(x) = 1$ т. и т. т., когда $x=i$

Это не отменяет того, что существует функции, невычислимые с помощью традиционного понятия алгоритма - если Вам не нравятся машины Тьюринга (мне они тоже не очень-то нравятся), то можно взять частично-рекурсивные функции.

-- Ср фев 10, 2010 01:31:35 --

Андрей АK в сообщении #286832 писал(а):

Нет, уже успел ответить.

Да, я тоже уже понял, что сглупил.

[Андрей АK]

Xaositect в сообщении #286835 писал(а):

Это не отменяет того, что существует функции, невычислимые с помощью традиционного понятия алгоритма - если Вам не нравятся машины Тьюринга (мне они тоже не очень-то нравятся), то можно взять частично-рекурсивные функции.

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

Это явно не классический "конечный" алгоритм.
Но тогда его "классическая невычислимость" означает только то, что в рамках "конечных алгоритмов" такой функции реализовать нельзя.
А вовсе не то что этот алгоритм невычислим.
Т.е. контрпример некорректен.

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

[Xaositect]

Андрей АK в сообщении #286837 писал(а):

Но тогда его "классическая невычислимость" означает только то, что в рамках "конечных алгоритмов" такой функции реализовать нельзя.
А вовсе не то что этот алгоритм невычислим.

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

[Андрей АK]

Xaositect в сообщении #286840 писал(а):

Андрей АK в сообщении #286837 писал(а):

Но тогда его "классическая невычислимость" означает только то, что в рамках "конечных алгоритмов" такой функции реализовать нельзя.
А вовсе не то что этот алгоритм невычислим.

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

Хорошо, тут я согласен.
Но тогда я переформулирую свои "претензии".
То что для каких-то "фантастических" функций может не быть алгоритма - это понятно и без всяких теорем.
От подобной теоремы хотелось бы ожидать, что она подтвердит или опровергнет существование алгоритмов для любой "нормальной" функции.
Т.е. для непротиворечивой ,с точки зрения математики, функции.
А здесь в качестве контрпримера предлагается функция, которая фактически ссылается на саму себя.
Т.е. нумерация всех алгоритмов происходит в первую фазу ,создания нашей функции, а потом ,на основе, созданного каталога, пердлагается создать некую производную от него функцию и после этого доказывается, что у алгоритма этой ,новой функции, в нашем старом каталоге - отсутсвует номер!
Но это же пример некорректной функции!
Можно сказать - особый случай.
И вот на основе этого особого случая делается вывод, что и все остальные алгоритмы (для нормальных функций) ВООБЩЕ - в принципе нереализуемые сущности.
Но это же - неправда.
Для любой "нормальной" функции - всегда есть алгоритм (конечный или бесконечный - это уже другой вопрос).
К стати, это доказательство - я бы назвал доказательством неперечислимости всех алгоритмов, а не их невычислимости.