О полноте и непротиворечивости

Существует ли доказательство что теорема Геделя также действительна для машин Тьюринга, а не только для алгебраических систем? Сходу ничего не нашел.

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

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

Комментарии

Причем здесь

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

Изображение пользователя Serguei_Tarassov.

Не совсем

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

Если

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

Изображение пользователя pater_leo.

Еще раз !

У Стэффорда Бира в книге "Кибернетика и менеджмент" - http://www.edurss.ru/cgi-bin/db.pl?cp=&p......
целая глава посвящена преодолению "принципа неполноты" Геделя в системах управления через "Принцип Внешнего Дополнения" , который впоследствии Бир развил до "алгедоничекского контура управления " в VSM .
»

Довольно

Довольно интересный разбор полётов на эту (или, по крайней мере, достаточно близкую) тему можно почитать здесь:
http://dima78.livejournal.com/tag/penrose
Читать, естественно, нужно снизу-вверх.

По мне так

По мне так главное в теореме Геделя, это то, что формальная система не может судить об истинности самой себя. т.е. её начнёт капитально глючит при попытке глубокой саморефлексии.

это можно переформулировать так - можно ли построить программу на любой вычислительной базе, которые даёт нам физика, чтобы эта программа 100% была защищена от сбоев?

будучи всю сознательную жизнь программистом, могу точно сказать - нельзя :)

даже если удастся построить гипотетический алгоритм с полной самопроверкой (что нельзя по теореме Гёделя) он наткнётся на физические ограничения, которые я здесь расписывал. даже если под вычислительную машину пристроить каждый квант, каждое физическое явление нашего мироздания, это не даст 100% свободы от ошибок, потому что внутри самого себя алгоритм не может судить об истинности самого себя, это может сделать только кто-то извне (хотя истинность этого внешнего тоже непонятна).

Пенроуз настаивает на том, что есть физические процессы, которые могут такое делать за конечное время (решать невычислимые задачи, вроде раскрутки саморефлексии или 100% проверки от ошибок), и мозг может дёргать эти процессы. Агументируя это тем, что мозг может решать невычислимые задачи.

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

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

Изображение пользователя pater_leo.

Еще раз !

Повторяю !
==========
У Стэффорда Бира в книге "Кибернетика и менеджмент" - http://www.edurss.ru/cgi-bin/db.pl?cp=&p......
целая глава посвящена преодолению "принципа неполноты" Геделя в системах управления через "Принцип Внешнего Дополнения" , который впоследствии Бир развил до "алгедоничекского контура управления " в VSM .
»

Изображение пользователя pater_leo.

У Стэффорда

У Стэффорда Бира в книге "Кибернетика и менеджмент" - http://www.edurss.ru/cgi-bin/db.pl?cp=&p...
целая глава посвящена преодолению "принципа неполноты" Геделя в системах управления через "Принцип Внешнего Дополнения" , который впоследствии Бир развил до "алгедоничекского контура управления " в VSM .

Изображение пользователя Serguei_Tarassov.

Я забыл

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