Comments 14
Еще хороший пример — проблема соответствий Поста. На гитхабе есть её решалка даже.
Впервые прочитал про эту задачу в 80-х в журнале «Scientific American» (русский вариант выходил под названием «В мире науки»). Кому любопытно взглянуть — статья в рубрике «Занимательный компьютер», посвящённая «охоте на бобра-работягу» в номере 1984-10, читательские отклики в номере 1985-05.
Как пример машин вне Тьюринга мне припоминаются нейронные сети. Вроде, даже слышал, что на них проблема самоостанова решается, но утверждать не берусь.
Кстати, а квантовый ассемблер относится к таким?
Кстати, а квантовый ассемблер относится к таким?
Нейронными сетями для постройки супертьюринговых машин занимается Hava Siegelmann. Вот одна из ее публикаций The Super-Turing Computational Power of plastic Recurrent Neural Networks, но на практике еще никому не удалось создать машины для гипервычислений. Квантовые модели тоже не позволяют этого сделать.
А вот вам еще одна головоломка про машину Тьюринга:
Не для всех программ, реализующих функции из натуральных в множество {0,1}, есть способ выяснить, останавливаются ли они на каждом аргументе или нет. Однако для некоторых таких программ существуют доказательства того, что они останавливаются. Процесс же поиска всех таких доказательств, как, наверное, известно читателям, всегда можно переложить на некоторую МТ, а значит множество программ, реализующих упомянутые функции и имеющих доказательство своей всюду определенности, алгоритмически перечислимо. Давайте построим МТ, перечисляющую для них пары (текст алгоритма, доказательство), и определим новую функцию G(n): она равна на n-том аргументе 1, если n-тая функция равна на нем 0 и наоборот. Читатель должен видеть, что задающий эту функцию алгоритм, не только всюду определен, но и имеет доказательство своей всюду определенности и конечно же не может совпадать ни с одним из имеющихся в списке!
Есть ли решение у этого парадокса?
Не для всех программ, реализующих функции из натуральных в множество {0,1}, есть способ выяснить, останавливаются ли они на каждом аргументе или нет. Однако для некоторых таких программ существуют доказательства того, что они останавливаются. Процесс же поиска всех таких доказательств, как, наверное, известно читателям, всегда можно переложить на некоторую МТ, а значит множество программ, реализующих упомянутые функции и имеющих доказательство своей всюду определенности, алгоритмически перечислимо. Давайте построим МТ, перечисляющую для них пары (текст алгоритма, доказательство), и определим новую функцию G(n): она равна на n-том аргументе 1, если n-тая функция равна на нем 0 и наоборот. Читатель должен видеть, что задающий эту функцию алгоритм, не только всюду определен, но и имеет доказательство своей всюду определенности и конечно же не может совпадать ни с одним из имеющихся в списке!
Есть ли решение у этого парадокса?
Думаю, слабое место этого парадокса в том, что не удастся создать такую аксиоматическую теорию, которая сможет доказать останавливаемость всех программ, из множества тех, что останавливаются.
А доказательство остановки G(n) лежит в плоскости другой аксиоматики, отличной от той, что используется изначально.
Хорошо, попытаюсь объяснить.
Вся математика с начала прошлого века попыталась стать формальной. С этого времени доказательства проводятся в формальных аксиоматических системах, которые суть
1. некоторый способ составлять слова и предложения из печатных символов, этот способ задает язык теории, причем проверка, является ли некоторая цепочка символов словом или предложением, должна быть выполнима всегда завершающимся алгоритмом, одним для всех цепочек.
2. формальных правил вывода, позволяющим из всякого семейства предложений, взятых в качестве первоначальных, выводить (продуцировать) другие предложения. На процесс продуцирования налагается то же требование алгоритмичности, что и в пункте 1.
3. Некоторого начального семейства формул, называемых аксиомами. Это семейство не обязательно должно быть конечным, однако должен быть предъявлен алгоритм, позволяющий для всякого предложения языка эффективно выяснить, является оно аксиомой или нет.
Формула языка называется доказанной, если она аксиома либо получена из аксиом и уже доказанных формул.
Основной прием предыдущего парадокса состоит в том, что все программы МТ, для которых существует доказательство конечности времени выполнения на каждом натуральном числе, можно выписать на листке бумаги в ряд (алгоритмически перечислить). Для этого будем перебирать все цепочки из букв и пробелов и алгоритмически проверять не является ли каждая из них доказательством конечности выполнения некоторой программы МТ на всех натуральных числах. Как только вы обнаружили очередное доказательство, проверьте нет ли указанной в нем программы в вашем списке, если нет — добавьте в него программу и найденное доказательство. Утверждается, что если программа имеет доказательство конечности своего выполнения на каждом натуральном числе, то рано или поздно вы на него наткнетесь и она таким образом попадет в список.
Конечно «существуют» программы, которые завершаются на любом натуральном числе, но этот факт никак нельзя доказать, однако для приведенного парадокса этот факт не имеет значения.
Вся математика с начала прошлого века попыталась стать формальной. С этого времени доказательства проводятся в формальных аксиоматических системах, которые суть
1. некоторый способ составлять слова и предложения из печатных символов, этот способ задает язык теории, причем проверка, является ли некоторая цепочка символов словом или предложением, должна быть выполнима всегда завершающимся алгоритмом, одним для всех цепочек.
2. формальных правил вывода, позволяющим из всякого семейства предложений, взятых в качестве первоначальных, выводить (продуцировать) другие предложения. На процесс продуцирования налагается то же требование алгоритмичности, что и в пункте 1.
3. Некоторого начального семейства формул, называемых аксиомами. Это семейство не обязательно должно быть конечным, однако должен быть предъявлен алгоритм, позволяющий для всякого предложения языка эффективно выяснить, является оно аксиомой или нет.
Формула языка называется доказанной, если она аксиома либо получена из аксиом и уже доказанных формул.
Основной прием предыдущего парадокса состоит в том, что все программы МТ, для которых существует доказательство конечности времени выполнения на каждом натуральном числе, можно выписать на листке бумаги в ряд (алгоритмически перечислить). Для этого будем перебирать все цепочки из букв и пробелов и алгоритмически проверять не является ли каждая из них доказательством конечности выполнения некоторой программы МТ на всех натуральных числах. Как только вы обнаружили очередное доказательство, проверьте нет ли указанной в нем программы в вашем списке, если нет — добавьте в него программу и найденное доказательство. Утверждается, что если программа имеет доказательство конечности своего выполнения на каждом натуральном числе, то рано или поздно вы на него наткнетесь и она таким образом попадет в список.
Конечно «существуют» программы, которые завершаются на любом натуральном числе, но этот факт никак нельзя доказать, однако для приведенного парадокса этот факт не имеет значения.
Я очень рад, что вам удалось решить этот парадокс, и мне хотелось бы по этому поводу указать на некоторые его следствия и добавить пару комментариев к решению.
На сегодняшний день в математике не используются языки, объектами высказываний которых были бы значения предложений самих этих языков, поэтому, как вы правильно заметили, доказательство всюду определенности G(n) не может быть проведено внутри никакой из современных теорий, если та использовалась для построения участвующего в парадоксе списка. Однако, математики никогда не ограничивали себя одной какой-либо теорией и не гнушаются на ходу придумать одну-другую, лишь бы с их помощью решалась стоящая перед ними на тот момент задача. Скорее, у каждого из них имеется некоторый запас доказательных методов и неформальных «истин», в которые они верят. В таком свете, приведенный парадокс показывает, что если вы имеете некоторый набор самоочевидных для вас доказательных методов, то все равно этот набор не включает достаточно самоочевидного относительно этого набора диагонального метода, участвующего в парадоксе.
Второе замечание — а собственно чем так плохи языки, способные высказываться о значении своих предложений и как решается парадокс в этом случае? Вы можете шаг за шагом попытаться представить в этом случае алгоритм действий, описанный в парадоксе. Скажем, вы уже нашли первые сто программ с доказательствами их всюду определенности и вот теперь смотрите на предложение, которое описывает диагональную конструкцию. Задает ли оно функцию и является ли тогда доказательством ее всюду определенности? Если предположить, что «да», то поставив его на сто первое место в списке, вы тут же придете к противоречию, если же вы решите «нет» и не поместите его в список, то с этого самого момента оно начнет задавать всюду определенную функцию и быть доказательством ее всюду определенности.
Все это было бы простой забавой и ненужным софизмом, если бы человечество остро не нуждалось в языках, способных высказываться о собственном значении в связи с задачами восприятия и мышления (описывая что-то, вы всегда можете описать и ваш язык описания, а размышляя над чем-то, размышлять над ходом мыслей). Но пока революция в основаниях математики только зреет.
На сегодняшний день в математике не используются языки, объектами высказываний которых были бы значения предложений самих этих языков, поэтому, как вы правильно заметили, доказательство всюду определенности G(n) не может быть проведено внутри никакой из современных теорий, если та использовалась для построения участвующего в парадоксе списка. Однако, математики никогда не ограничивали себя одной какой-либо теорией и не гнушаются на ходу придумать одну-другую, лишь бы с их помощью решалась стоящая перед ними на тот момент задача. Скорее, у каждого из них имеется некоторый запас доказательных методов и неформальных «истин», в которые они верят. В таком свете, приведенный парадокс показывает, что если вы имеете некоторый набор самоочевидных для вас доказательных методов, то все равно этот набор не включает достаточно самоочевидного относительно этого набора диагонального метода, участвующего в парадоксе.
Второе замечание — а собственно чем так плохи языки, способные высказываться о значении своих предложений и как решается парадокс в этом случае? Вы можете шаг за шагом попытаться представить в этом случае алгоритм действий, описанный в парадоксе. Скажем, вы уже нашли первые сто программ с доказательствами их всюду определенности и вот теперь смотрите на предложение, которое описывает диагональную конструкцию. Задает ли оно функцию и является ли тогда доказательством ее всюду определенности? Если предположить, что «да», то поставив его на сто первое место в списке, вы тут же придете к противоречию, если же вы решите «нет» и не поместите его в список, то с этого самого момента оно начнет задавать всюду определенную функцию и быть доказательством ее всюду определенности.
Все это было бы простой забавой и ненужным софизмом, если бы человечество остро не нуждалось в языках, способных высказываться о собственном значении в связи с задачами восприятия и мышления (описывая что-то, вы всегда можете описать и ваш язык описания, а размышляя над чем-то, размышлять над ходом мыслей). Но пока революция в основаниях математики только зреет.
Sign up to leave a comment.
Невычислимые функции на примере Busy Beaver Game