Пишет st,
Существует ли доказательство что теорема Геделя также действительна для машин Тьюринга, а не только для алгебраических систем? Сходу ничего не нашел.
Отсутствие доказательства означает, в частности, что для обучения нейросети может существовать алгоритм, созданный на базе тех же нейросетевых механизмов. Или, возвращаясь к дискуссии о познании, что теоретически возможен "супермозг", в пределе познавший Вселенную.
Опровергающая цепочка рассуждений "машина Тьюринга равномощна нормальному алгоритму Маркова, алгортм Маркова основан на формальном языке на который распространяется теорема Геделя" не работает, т.к. в формальном языке нет понятия указателей (см. также дискуссию на мембране).
Комментарии
Причем здесь
Пишет xp_cmdshell (не проверено),
Причем здесь алгебраические системы и машины Тьюринга? Доказательство теоремы Гёделя справедливо для любого исчисления, содержащего в качестве подмножества формальную арифметику. Формальная арифметика реализуется на машине Тьюринга, потому что любая частично-рекурсивная функция вычислима на машине Тьюринга, а всякая функция, вычислимая на машине Тьюринга, является частично-рекурсивной.
Не совсем
Пишет st,
Формальная арифметика реализуется на машине Тьюринга, но, насколько я знаю, она не является ее (машины) подмножеством.
Если
Пишет xp_cmdshell (не проверено),
Если выражаться корректно, то формальная система, которую можно реализовать на машине Тьюринга, может содержать в качестве подмножества формальную арифметику. С другой стороны, любую программу для машины Тьюринга можно представить в виде нескольких функций формальной арифметики. Это приводит к тому, что, с одной стороны, можно запрограммировать на машине Тьюринга доказательство теоремы некоторой формальной теории, а с другой стороны, нельзя определить, завершится ли когда нибудь это доказательство. Таким образом, теорема Гёделя в случае машин Тьюринга сводится к проблеме останова: построить такую программу, которая для любой заданной программы определяла, завершится когда-нибудь заданная программа или нет. Проблема останова, как известно, неразрешима. Суть тут в том, что в любой формализации понятия алгоритма вычислимые функции являются частичными, т.е. они определены не всюду, и невозможно продолжение до функций, определенных всюду. Это связано с тем, что любая формализация понятия алгоритма должна содержать аналог оператора while, и заранее нельзя сказать когда завершится программа и завершится ли она вообще.
Еще раз !
Пишет pater_leo,
У Стэффорда Бира в книге "Кибернетика и менеджмент" - http://www.edurss.ru/cgi-bin/db.pl?cp=&p......
целая глава посвящена преодолению "принципа неполноты" Геделя в системах управления через "Принцип Внешнего Дополнения" , который впоследствии Бир развил до "алгедоничекского контура управления " в VSM .
»
Довольно
Пишет Анисимов В.А. (не проверено),
Довольно интересный разбор полётов на эту (или, по крайней мере, достаточно близкую) тему можно почитать здесь:
http://dima78.livejournal.com/tag/penrose
Читать, естественно, нужно снизу-вверх.
В тему
Пишет st,
Очень интересно, спасибо
По мне так
Пишет dima78.livejour... (не проверено),
По мне так главное в теореме Геделя, это то, что формальная система не может судить об истинности самой себя. т.е. её начнёт капитально глючит при попытке глубокой саморефлексии.
это можно переформулировать так - можно ли построить программу на любой вычислительной базе, которые даёт нам физика, чтобы эта программа 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 .
Я забыл
Пишет st,
Я совсем забыл про это, из головы вылетело, хотя даже на листочке заметок к книге сие было отмечено. Спасибо, что напомнили.