?

Log in

No account? Create an account

Previous Entry | Next Entry

Гедель 1

 1   2  3  4  5  6  7

I. Введение

Часто приходится слышать, будто бы некая «теорема Геделя» якобы доказывает, что процессы в сознании вообще и мышление в частности не могут быть алгоритмизированы и смоделированы на вычислительной машине. Многие пускаются в весьма пространные рассуждения, будто бы доказывающие это. Во всех этих рассуждениях непременно обнаруживается логический изъян. Несмотря на обилие таких рассуждений, безупречного доказательства того, что вычислительные формализмы не способны охватить когнитивные процессы, не существует. Не существует, однако, и доказательства обратного — что сознание описуемо формальной системой; к этому мы обратимся в самом конце.

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

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

II. Библиография

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

1. Хофштадтер Д. Гедель, Эшер, Бах. Самара : Бахрах-М, 2001. Книга эта подобна фуге, где параллельные голоса создают гармонию смыслов. Одна из тем — рассказ о теоремах Геделя и неразрешимости.

2. Подниекс К. М. Вокруг теоремы Геделя. Рига : Зинатне, 1981. Это замечательное математическое введение в теоремы Геделя; там же вы найдете их доказательство, которое мы здесь разбирать не будем. О применимости их к сознанию, однако, в книге не говорится.

3. Franzén T. Gödel's Theorem: An Incomplete Guide to its Use and Abuse. Wellesley, Mass. : AK Peters, 2005 (спасибо alexey_rom за ссылку). Книга написана несколько менее популярно, чем [1], и требует определенных математических знаний, но в ней разбираются и те вопросы, что мы разбираем сейчас.

III. Смертен ли Сократ?

Теоремой или теоремами Геделя обычно называют совокупность утверждений о неполноте арифметик, начало которым было положено Куртом Геделем в работе, опубликованной в 1931 г., а затем значительно усиленных другими математиками; в частности, более сильное утверждение, которое чаще всего сегодня и называют теоремой Геделя (в единственном числе) доказано Баркли Россером, учеником Алонцо Черча, в 1936 г.

Чтобы понять теорему Геделя, сначала следует разобраться в предмете, котором она говорит, а говорит она о формальных системах (ФС). ФС, как следует из их названия, имеют дело с формой. Понятие формы, отдельно рассматриваемой от сущности предмета, восходит к философии Аристотеля; он же и изобрел формализмы — силлогизмы:

Каждый человек смертен.
Сократ — человек.
Следовательно, Сократ смертен.

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

Все P есть Q.
R есть P.
Следовательно, R есть Q.

Мотив разделения формы и смысла будет центральным в нашем повествовании. Обратите внимание еще раз: сам по себе формальный силлогизм никакого смысла не имеет: вывод «следовательно, R есть Q» совершенно бессмыслен, покуда R и Q не заменены на определенные высказывания. В то же время, смысл возникает при интерпретации формализма, но не в самом формализме. Мы, снаружи формализма, придаем высказываниям смысл. Мы говорим, что все люди смертны, и что Сократ есть человек. После этого мы берем Аристотелев формализм — как инструмент — и подставляем в него эти утверждения, и получаем вывод: Сократ смертен. Где возникает этот вывод? Следите сейчас очень внимательно: этот вывод не возникает в формализме, он возникает лишь при интерпретации результата исполнения формальной процедуры! Формализм лишь выдает предложение, строчку текста: «Сократ смертен». Однако, сами по себе понятия «Сократ» и «быть смертным» существуют лишь вне формализма, в сознании интерпретирующего.

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

Введите P: человек
Введите Q: смертен
Введите R: Сократ


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

Сократ смертен

Радиоактивные пришельцы на самом деле обладают одним бессмертным «я» на всех, как Борг из «Звездного пути», но называют себя, по случайному совпадению, не Боргом, а Сократом. Верное на наш взгляд утверждение оказывается для них прямо ложным. Выходит, истинность утверждения зависит от этого самого взгляда. Формализм генератора верных утверждений из верных посылок сработал, но верного по смыслу утверждения не выдал — потому, что нет того, кто бы интерпретировал посылки и утверждение как истинное. Со сменой точки зрения и предпосылка «Сократ есть человек», и вывод «Сократ смертен» превращаются из истинных в ложные.

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

IV. Кубики для взрослых

Построим простую ФС, которую будем называть «система ХИХИ»1. Возьмем неограниченный запас кубиков или табличек с буквами Х, А, И. Хоть общее число кубиков неограниченно, но на них встречаются только три этих буквы. Множество { Х, А, И } называется лексическим множеством или алфавитом ФС. Алфавит системы должен быть, по правилам игры в кубики, конечным множеством.

Из кубиков можно составить строки ФС. Например, из наших кубиков можно сложить строки ХИХИХИ, ИАИА, ХХХХХХ и АХ. Эти строки будут лексически верными. Строка АГА, в то же время, не является лексически верной, потому что Г не входит в алфавит системы ХИХИ.

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

Во первых, зададим начальное подмножество верных строк извне, по нашему произволу 2. Для нашей игры в кубики скажем, что строка ХИ верна3.

Во-вторых, введем несколько правил замены строк. Эти правила строго формальны — их легко исполнять не задумываясь, а задачу запрограммировать их на компьютере решит любой школьник на «пять». Важно помнить, что эти правила верны только для верных строк: из верной строки получается верная. К неверным, синтаксически или, еще страшнее того, лексически недопустимым строкам эти правила применять запрещается. Набор правил всегда конечный: «правила, порождающие правила» не разрешаются. Для нашей системы введем следующие правила4:

1. К любой строке, заканчивающейся на И, можно дописать в конец А. Пример: ХИХИХИХИА.
2. Подстроку, следующую за Х {доб. до конца всей строки}, можно удвоить: ХИХИИ, ХАХИХАХИАХИ, ХАХИХАХИИ.
3. Три И подряд можно заменить на А: ХИИИИХИА, ХИИИИХАИ.
4. Две А подряд можно выбросить: ИААХИХ, ИАААИИАИ.

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

ХИХИИ (правило 2),
ХИИХИИИИ (опять 2),
ХИИИИХАИ (3),
ХАИХАИА (1),

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

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

Здесь нам следует еще раз вспомнить о том, что никакого смысла в верных строках ФС нет. ФС может служить инструментом для переработки смыслов, вкладываемых в строки извне системы, но она ни содержит, ни производит смысла. Слова, сложенные из кубиков, не имеют никакого особого значения: это только слова, сложенные из кубиков.

Перед тем, как мы перейдем к следующей части, попробуйте продолжить нашу игру в кубики. Требуется определить, является ли ХА верной строкой в системе ХИХИ. Либо в ее произведете по правилам 1—4 из других заведомо верных строк (в нашем случае из заведомо верной строки ХИ), либо докажете, что этого сделать невозможно. Решение — или, не огорчайтесь, даже попытка решения этой задачи сразу даст вам почувствовать, какие сложности возникают даже в таких простых ФС, как наша система ХИХИ.

 1   2  3  4  5  6  7
__________________________________
1. Hofstadter 1999, p. 33.

2. Это множество может быть конечным или даже бесконечным. Бесконечное множество может получаться из правила, например, в некоей системе, где Ы входит в алфавит, строки любой длины из Ы могут быть объявлены верными. Такие правила называются схемами.

3. Не удивляйтесь, что мы обойдемся без обычных в описании ФС терминов «аксиома» и «теорема», которые скорее внесли бы в это популярное изложение путаницу, нежели ясность, отсылая читателя к омонимичным, но иным понятиям школьной математики.

4. Те, кто интересуется формальными грамматиками, должны заметить, что правила представляют собой контекстно-зависимую грамматику. Не любая ФС обладает контекстно-свободной грамматикой (КСГ), потому что вычислительная мощность ФС та же, что и у машины Тьюринга и, следовательно, неизбежно превышает таковую стековой машины, выражающей КСГ.

5. Счетное множество возможно бесконечно, но его элементы можно перенумеровать натуральными числами — разумеется, применяя определенное правило. К примеру, множество целых чисел счетно, а нумеровать их можно так: у числа 0 будет номер 1, у 1 номер 2, у −1 номер 3, у 2 номер 4, и так далее: у положительных четные номера, у соответствующих отрицательных нечетные на единицу больше.

Кантор доказал, что множество рациональных дробей, то есть чисел вида p/q, где p и q натуральные числа, тоже счетно, придумав элегантный способ пронумеровать их. Этот способ называется «диагональным аргументом». Попробуйте и вы придумать такой способ. Счетность множества верных строк тоже доказывается диагональным аргументом.

Tags:

Comments

( 151 comments — Leave a comment )
Page 1 of 2
<<[1] [2] >>
tvzolotova
Dec. 11th, 2009 05:40 am (UTC)
индиго
мир познаваем...
arno1251
Dec. 11th, 2009 06:06 am (UTC)
Выражение "пробило на хихи" внезапно заиграло новыми красками...
fregimus
Dec. 11th, 2009 02:46 pm (UTC)
Боюсь даже подумать, на что может пробить в следующей части…
schegloff
Dec. 11th, 2009 06:07 am (UTC)
Замечательно!
Пожалуй, лучшее описание "теоремы Геделя" из всех, что я читал. Тот самый случай, когда правильная постановка задачи - 90% ее решения. Не зря я Вас подбивал на эту статью :)
fregimus
Dec. 12th, 2009 02:43 am (UTC)
Да мы еще к теореме-то и близко не подобрались. Попробую объяснить популярно, конечно, но сложно это все.
В принципе ухватил - ngc4594 - Dec. 15th, 2009 03:36 pm (UTC) - Expand
Re: В принципе ухватил - fregimus - Dec. 15th, 2009 05:56 pm (UTC) - Expand
yurvor
Dec. 11th, 2009 06:40 am (UTC)
Прочитал пока только про Сократа, но уже не согласен :) Или мягче говоря, у меня вопросы. Главный из них, конечно - что есть смысл?

Итак, "смысла формальные системы не содержат и не производят". Однако, есть возражение.

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

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

Но как только мы заимели формализм, и скормили ему на вход осмысленно-верные фразы A и B, он нам выдал осмысленно-верную фразу C. Ясное дело, что с участием формализма что-то изменилось. Без нас, понимающих A, B и C, конечно, не обошлось. Но и формализм внёс свою лепту в увеличение смысла.

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

Ваш ход, маэстро!
fregimus
Dec. 12th, 2009 02:46 am (UTC)
А это всегда вопрос, где границу провести. Мне для этого рассуждения надо провести ее именно здесь; bear with me. Дальше я ее сдвину, stay tuned.

Если мы (C) напечатаем, в конверт заклеим и никому не покажем — можно ли сказать, что счысл уже «образовлася», только он заклеен в конверте и его еще никто не получил? Или смысл возникнет только после того, как кто-то распечатает конверт и прочитает утверждение?
(no subject) - yurvor - Dec. 15th, 2009 04:24 pm (UTC) - Expand
возражение не понял - rombell - Dec. 13th, 2009 12:37 pm (UTC) - Expand
Re: возражение не понял - pagankz - Dec. 13th, 2009 02:02 pm (UTC) - Expand
Re: возражение не понял - yurvor - Dec. 15th, 2009 04:37 pm (UTC) - Expand
Re: возражение не понял - yurvor - Dec. 15th, 2009 04:31 pm (UTC) - Expand
Re: возражение не понял - gdt - Dec. 15th, 2009 05:18 pm (UTC) - Expand
Re: возражение не понял - yurvor - Dec. 15th, 2009 05:25 pm (UTC) - Expand
Re: возражение не понял - gdt - Dec. 15th, 2009 06:14 pm (UTC) - Expand
Re: возражение не понял - yurvor - Dec. 16th, 2009 05:31 am (UTC) - Expand
Re: возражение не понял - gdt - Dec. 16th, 2009 03:57 pm (UTC) - Expand
Re: возражение не понял - yurvor - Dec. 16th, 2009 08:32 pm (UTC) - Expand
Re: возражение не понял - gdt - Dec. 17th, 2009 12:56 pm (UTC) - Expand
Re: возражение не понял - yurvor - Dec. 17th, 2009 05:07 pm (UTC) - Expand
Re: возражение не понял - gdt - Dec. 18th, 2009 10:10 am (UTC) - Expand
Re: возражение не понял - yurvor - Dec. 18th, 2009 04:28 pm (UTC) - Expand
Re: возражение не понял - gdt - Dec. 18th, 2009 04:39 pm (UTC) - Expand
Re: возражение не понял - yurvor - Dec. 18th, 2009 05:22 am (UTC) - Expand
Re: возражение не понял - gdt - Dec. 18th, 2009 10:01 am (UTC) - Expand
Re: возражение не понял - yurvor - Dec. 18th, 2009 04:26 pm (UTC) - Expand
Re: возражение не понял - gdt - Dec. 18th, 2009 04:39 pm (UTC) - Expand
Re: возражение не понял - yurvor - Dec. 18th, 2009 04:41 pm (UTC) - Expand
Re: возражение не понял - gdt - Dec. 18th, 2009 04:54 pm (UTC) - Expand
Re: возражение не понял - yurvor - Dec. 18th, 2009 05:47 pm (UTC) - Expand
Re: возражение не понял - gdt - Dec. 18th, 2009 05:56 pm (UTC) - Expand
Re: возражение не понял - yurvor - Dec. 18th, 2009 06:02 pm (UTC) - Expand
Re: возражение не понял - gdt - Dec. 18th, 2009 07:53 pm (UTC) - Expand
Re: возражение не понял - yurvor - Dec. 18th, 2009 08:06 pm (UTC) - Expand
Re: возражение не понял - gdt - Dec. 18th, 2009 08:34 pm (UTC) - Expand
Re: возражение не понял - yurvor - Dec. 18th, 2009 08:45 pm (UTC) - Expand
Re: возражение не понял - fregimus - Dec. 19th, 2009 01:25 am (UTC) - Expand
Re: возражение не понял - pagankz - Dec. 18th, 2009 09:45 pm (UTC) - Expand
Re: возражение не понял - fregimus - Dec. 19th, 2009 01:23 am (UTC) - Expand
Re: возражение не понял - yurvor - Dec. 19th, 2009 04:27 am (UTC) - Expand
Я ПОНЯЛ ГЛАВНУЮ ФИШКУ - yurvor - Dec. 20th, 2009 01:02 pm (UTC) - Expand
Re: Я ПОНЯЛ ГЛАВНУЮ ФИШКУ - gdt - Dec. 20th, 2009 02:09 pm (UTC) - Expand
Re: Я ПОНЯЛ ГЛАВНУЮ ФИШКУ - gdt - Dec. 21st, 2009 09:16 am (UTC) - Expand
Re: Я ПОНЯЛ ГЛАВНУЮ ФИШКУ - yurvor - Dec. 21st, 2009 04:44 am (UTC) - Expand
Re: Я ПОНЯЛ ГЛАВНУЮ ФИШКУ - gdt - Dec. 21st, 2009 09:07 am (UTC) - Expand
Re: Я ПОНЯЛ ГЛАВНУЮ ФИШКУ - yurvor - Dec. 21st, 2009 01:43 pm (UTC) - Expand
Re: Я ПОНЯЛ ГЛАВНУЮ ФИШКУ - gdt - Dec. 22nd, 2009 07:39 am (UTC) - Expand
Re: возражение не понял - gdt - Dec. 21st, 2009 10:20 am (UTC) - Expand
Re: возражение не понял - yurvor - Dec. 21st, 2009 03:15 pm (UTC) - Expand
Re: возражение не понял - rombell - Dec. 15th, 2009 05:57 pm (UTC) - Expand
Re: возражение не понял - yurvor - Dec. 16th, 2009 05:24 am (UTC) - Expand
yurvor
Dec. 11th, 2009 06:53 am (UTC)
А в ответ на твоё ХА сердце мне подсказывает, что играет роль число 196 :)

Edited at 2009-12-11 06:59 am (UTC)
yurvor
Dec. 11th, 2009 09:01 pm (UTC)
196 - это чушь, конечно. С прямым углом спутал :)
(no subject) - fregimus - Dec. 12th, 2009 02:46 am (UTC) - Expand
cryozot
Dec. 11th, 2009 06:57 am (UTC)
Начало интересное, но задачка простая. По крайней мере, если я ничего не напутал. Строка ХА является верной в системе ХИХИ, поскольку полчается из "априорно" верной ХИ путём двойного применения правила замены №2 и однократного -- №3. А вот верность ХАХА из верности ХИ по данным правилам уже никак не выведешь.
randomisator
Dec. 11th, 2009 07:34 am (UTC)
Что получается из ХИ путём двойного применения правила замены №2 и однократного - №3 написано в тексте, это не ХА;)
(no subject) - (Anonymous) - Dec. 11th, 2009 08:58 am (UTC) - Expand
(no subject) - (Anonymous) - Dec. 11th, 2009 07:41 am (UTC) - Expand
(no subject) - fregimus - Dec. 11th, 2009 03:04 pm (UTC) - Expand
(no subject) - cryozot - Dec. 11th, 2009 05:17 pm (UTC) - Expand
drevo_z
Dec. 11th, 2009 07:07 am (UTC)
Прекрасная статья Жду продолжения.
Однако я, похоже, запуталась.
Вот тот старый пример, когда из двух верных утверждений получается формально логически верное, но смысла не имеющее. Я его толком не помню, но так, приблизительно:.
У всех птиц две ноги.
У Сократа две ноги.
Следовательно, Сократ птица.
(Anonymous)
Dec. 11th, 2009 07:30 am (UTC)
Если совсем отключить мозг, то можно нагенерить еще больше подобных "логически верных" утверждений

У Васи две ноги
У Пети две ноги
Следовательно, Вася это Петя... или Петя это Вася... или все птицы - Сократы.
(no subject) - pagankz - Dec. 11th, 2009 07:52 am (UTC) - Expand
(no subject) - pagankz - Dec. 11th, 2009 07:48 am (UTC) - Expand
(no subject) - drevo_z - Dec. 11th, 2009 07:54 am (UTC) - Expand
randomisator
Dec. 11th, 2009 07:32 am (UTC)
ХА неверно
Сопоставим буквам значения Х=0, И=1, А=3. Преобразования 1,3,4 не изменяют остаток от деления на 3 суммы значений букв. Преобразование 2 изменяет остаток по закону 1->2, 2->1, 0->0. Для ХИ остаток 1, для ХА - 0. Значит ХА не является верной.
pagankz
Dec. 11th, 2009 07:43 am (UTC)
Ой ли?
ХИ->ХИИИ->ХА
Re: Ой ли? - randomisator - Dec. 11th, 2009 08:01 am (UTC) - Expand
Re: Ой ли? - pagankz - Dec. 11th, 2009 08:11 am (UTC) - Expand
Re: Ой ли? - pagankz - Dec. 11th, 2009 08:16 am (UTC) - Expand
Re: Ой ли? - randomisator - Dec. 11th, 2009 08:22 am (UTC) - Expand
Re: Ой ли? - fregimus - Dec. 11th, 2009 02:56 pm (UTC) - Expand
(no subject) - fregimus - Dec. 12th, 2009 02:47 am (UTC) - Expand
tvzolotova
Dec. 11th, 2009 07:38 am (UTC)
индиго
Киборгоизация межпространственного континиума - вопрос решенный три дня назад - это ближайшее чел- ва... Уж простите, без Вас порешала... Человеки, как сумма аргументов - решать железу...Никто уже не переиначит.. Свыкайтесь с мыслью...
pagankz
Dec. 11th, 2009 07:57 am (UTC)
Re: индиго
В данном контексте железо как бы и не при чем - у людей голова так же работает... Только не может совсем уж сложные выводы делать в силу естесственных природных ограничений
Re: индиго - pagankz - Dec. 11th, 2009 07:59 am (UTC) - Expand
miollnyr
Dec. 11th, 2009 08:19 am (UTC)
Кстати счетность строк можно намного проще доказать:)

У нас есть троичный алфавит, то бишь любой строке сооветствует натуральное число в троичной системе (заменим X на 0, A - 1, И на 2).
randomisator
Dec. 11th, 2009 08:25 am (UTC)
Преобразование неоднозначное - 01=001=0001, а строки разные. Вот в четверичной (Х=1, А=2, И=3) получается, учитывая что любое бесконечное подмножество множества натуральных чисел счётно.
(no subject) - miollnyr - Dec. 11th, 2009 08:30 am (UTC) - Expand
(no subject) - fregimus - Dec. 11th, 2009 03:01 pm (UTC) - Expand
(no subject) - miollnyr - Dec. 11th, 2009 03:03 pm (UTC) - Expand
(no subject) - fregimus - Dec. 11th, 2009 03:05 pm (UTC) - Expand
stefashka
Dec. 11th, 2009 08:24 am (UTC)
Немного в сторону
==>Часто приходится слышать, будто бы некая «теорема Геделя» якобы доказывает, что процессы в сознании вообще и мышление в частности не могут быть алгоритмизированы и смоделированы на вычислительной машине.

А невозможность построить алгоритм, определяющий конечность/бесконечность цикла разве не говорит о том, что человеческое мышление не воспроизводимо на выч.машинах?
fregimus
Dec. 11th, 2009 03:10 pm (UTC)
Проблема останова? Нет, не говорит — ее и человек не может решить.

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

Ну, и у людей те же самые проблемы. Если б это было не так, в софте ошибок бы не было.
ngc4594
Dec. 11th, 2009 08:29 am (UTC)
Вычислительные формализмы и когнитивные процессы
Если я не ошибаюсь, у Стаффорда Бира было доказательство, что жизнеспособная система не может являться конечным автоматом. Стало быть, поскольку человек является жизнеспособной системой, то его мышление неалгоритмизуемо.
cryozot
Dec. 11th, 2009 05:20 pm (UTC)
Re: Вычислительные формализмы и когнитивные процессы
Конечный автомат и алгоритмизуемость не одно и то же. Машина Тьюринга вместе со своей бесконечной лентой не является конечным автоматом.
Это не совсем то - ngc4594 - Dec. 15th, 2009 11:40 am (UTC) - Expand
Re: Это не совсем то - cryozot - Dec. 15th, 2009 01:47 pm (UTC) - Expand
Не опечатался - ngc4594 - Dec. 15th, 2009 02:17 pm (UTC) - Expand
Тёплое с мягким - cryozot - Dec. 15th, 2009 04:58 pm (UTC) - Expand
Стриженое с бритым - ngc4594 - Dec. 16th, 2009 03:33 pm (UTC) - Expand
(no subject) - fregimus - Dec. 12th, 2009 02:49 am (UTC) - Expand
yegor_nachinkin
Dec. 11th, 2009 08:46 am (UTC)
статья интересная,
и интересно было бы прочитать продолжение. Но -- как все такие статьи -- она в неявном виде содержит совершенно неверное предположение, будто человек мыслит силлогизмами Аристотеля. А это не так. Логика следует из человека, обратное не верно: человек не следует из логики. Возьмите в качестве вывода утверждение "красота спасёт мир" и попытайтесь найти посылки силлогизма.
ngc4594
Dec. 11th, 2009 09:03 am (UTC)
Вы смешиваете два понятия
А именно логику мышления и логику высказывания. Можно вполне алгоритмическим путём генерировать высказывания типа «красота спасёт мир», так, как это делает «робот Сергей Дацюк» или «Весна» на Яндексе.
я, извините, - yegor_nachinkin - Dec. 11th, 2009 09:24 am (UTC) - Expand
Re: я, извините, - pagankz - Dec. 11th, 2009 09:28 am (UTC) - Expand
совершенно верно, - yegor_nachinkin - Dec. 11th, 2009 09:35 am (UTC) - Expand
Re: совершенно верно, - pagankz - Dec. 11th, 2009 10:43 am (UTC) - Expand
Разумеется ИИ возможен - ngc4594 - Dec. 11th, 2009 01:24 pm (UTC) - Expand
А в чём трудность? - ngc4594 - Dec. 11th, 2009 02:12 pm (UTC) - Expand
Re: А в чём трудность? - pagankz - Dec. 11th, 2009 02:20 pm (UTC) - Expand
извиню :) - ngc4594 - Dec. 11th, 2009 11:40 am (UTC) - Expand
Re: извиню :) - pagankz - Dec. 11th, 2009 12:17 pm (UTC) - Expand
Религия и логика - ngc4594 - Dec. 11th, 2009 12:27 pm (UTC) - Expand
Вполен возможно - ngc4594 - Dec. 11th, 2009 02:15 pm (UTC) - Expand
Таки да - pagankz - Dec. 11th, 2009 02:29 pm (UTC) - Expand
вот на арену и вышел - yegor_nachinkin - Dec. 11th, 2009 07:16 pm (UTC) - Expand
Re: вот на арену и вышел - captainl - Dec. 12th, 2009 02:24 am (UTC) - Expand
именно - yegor_nachinkin - Dec. 12th, 2009 10:23 am (UTC) - Expand
Тут нет противоречия - ngc4594 - Dec. 15th, 2009 03:33 pm (UTC) - Expand
Re: Тут нет противоречия - captainl - Dec. 15th, 2009 04:11 pm (UTC) - Expand
Консенсус - ngc4594 - Dec. 16th, 2009 03:16 pm (UTC) - Expand
Re: статья интересная, - pagankz - Dec. 11th, 2009 09:08 am (UTC) - Expand
Re: статья интересная, - tvzolotova - Dec. 11th, 2009 09:26 am (UTC) - Expand
Re: статья интересная, - pagankz - Dec. 11th, 2009 09:31 am (UTC) - Expand
allambee
Dec. 11th, 2009 09:05 am (UTC)
спасибо за этот цикл, буду читать
janatem
Dec. 11th, 2009 09:43 am (UTC)
Ваше определение счетного множества не каноническое; по определению, счетное множество является бесконечным. Т.е. в тексте надо заменить "счетное" на "не более чем счетное".
fregimus
Dec. 11th, 2009 02:59 pm (UTC)
Спасибо, действительно так. Поправлю.
Page 1 of 2
<<[1] [2] >>
( 151 comments — Leave a comment )