Какое отношение имеют шахматные программы к искусственному интеллекту?

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

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

Давайте подумаем.
Т.е. Диагонолизатор не сможет остановиться потому что Анализатор зациклится посчитав Диагонализатор конечной программой, а это противоречие.

НО

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

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


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


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

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

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

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

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

http://ric.uni-altai.ru/Fundamental/teor-alg/upr15/upr15-4.htm

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

Из того что я понял по википедии, наверно всё это приведено более понятным языком чем в 1973 году с их лентами, диагонализатор остановится только потому что зациклится анализатор, но это по моему мнению не означает что диагонализатор бесконечен.

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

Доказательство такое: итак, алгоритм обладает такими свойствами: останавливается, если аргумент зацикливается. Зацикливается, если аргумент останавливается.

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

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

Парадоксы дедуктивной логики
http://ravil.astersoft.net/Students/AI/paradox.htm

Но какое это имеет отношение к анализатору?
Зацикливание не обязательное свойство анализатора, во вторых 2 программы не могут одновременно остановиться или одновременно зациклиться, в любой момент исполняется только одна из них.


Я до сих пор не получил опровержение того что

Так о чем я пытаюсь и рассказать Если предположить, что такой алгоритм существует, то получаем парадокс лжеца. Значит, такого алгоритма не существует.

Это просто формальное доказательство на приведенной выше идее.

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

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

Эта проблема есть если действительно перебирать все возможные варианты программ, и выбрать ту которая зацикливается если аргумент останавливается и останавливается если аргумент зацикливается, и проверить её на себе.

Может быть это имеет отношение к Теореме Гёделя о неполноте, т.о. искусственный интеллект не может всё знать и всё решать, но это уже такие дебри. :|



http://z-mech.narod.ru/Lib/chaitin2.html
2. Гедель, Тьюринг и диагональный процесс Кантора

Гильберт действительно вдохновлял. Известна его лекция в 1900 году призывавшая к оружию математиков на решение списка из двадцати трех труднейших математических проблем. Будучи юным отроком, избравшим путь математика, вы читаете этот список из двадцати трех проблем и слышите, как Гильберт говорит, что нет никаких ограничений тому, что математики могут открыт. Мы можем решить любую проблему, если достаточно умны и работаем над этим достаточно долго и упорно. Он предполагал, что нет никакого предел математическим достижениям.
Я думаю, это очень вдохновляло. Например, фон-Неймана. Когда он был молодым человеком, он предпринял попытку осуществить честолюбивый план Гильберта.
Поскольку Гильберт вряд ли мог заставить все это работать целиком, он фактически начинал с элементарной теории чисел, для начала с 1, 2, 3, 4, 5, … , даже не с действительных чисел, а с натуральных.
Но в 1931 году к великому и всеобщему удивлению (в том числе и фон-Неймана) Гедель показал, что это было невозможно, что это не могло быть сделано, по причине, о которой, я уверен, все знаете.

Гедель 1931

Это полностью противоречило тому, чего все ждали. Нейман сказал, что ему никогда в голову не приходило, что программа Гильберта не может быть выполнена. Фон-Нейман был крайне восхищен Геделем и помог ему получить положение в Институте Перспективных Исследований (Institute for Advanced Study).
Вот что следовало из того, что показал Гедель. Предположим, что вы имеете формальную аксиоматическую систему, имеющую дело с элементарной теорией чисел. С 1, 2, 3, 4, 5, сложением и умножением. И теперь предположим что такая система непротиворечива - это минимальное требование к ней (если вы действительно можете доказать в ней ложные утверждения, то это очень плохо!). Гедель показал, что еcли вы признаете, что система последовательна, то он может показать, что она неполна. Это был результат, полученный Геделем, и его доказательство очень остроумно использовало само-ссылку (само-референцию).
Гедель смог построить утверждение, относительно целых чисел, которое говорит о самом себе, что оно недоказуемо. Это был сокрушительный удар. Интеллектуальное воображение Геделя достойно восхищения! Ведь тогда каждый думал, что Гильберт прав.
Однако, я думаю, что подход Тьюринга все же был лучше.

Гедель 1931
Тьюринг 1936

Геделево доказательство 1931 года очень изобретательно, это действительно tour de force - проявление ловкости, силы ума и изобретательности. Должен признать, что когда я был юношей, пробовавшим понять все это, я мог читать это и следить за этим, шаг за шагом, но так или иначе я не мог никак почувствовать, что я улавливаю все это в целом. Но Тьюринг применил абсолютно иной подход.
Подход Тьюринга, и я думаю справедливо так говорить, является в некотором смысле более фундаментальным.
Фактически, Тьюринг делает больше чем Гедель. Тьюринг не только пришел к тому же заключению что и Гедель, но и показал, что не существует никакой разрешающей процедуры.
Смотрите. Если вы предполагаете, что у вас имеется формальная аксиоматическая система для арифметики, и она последовательна, то от Геделя вы знаете, что она не может быть полной. Но для нее все еще могла бы существовать разрешающая процедура. Все еще могла существовать некая механическая процедура, которая позволила бы вам решить является данное утверждение истинным или нет. Это все еще оставалось возможным после открытия Геделя. Но Тьюринг разрушил и это. Факт не существования разрешающей процедуры более фундаментален и тогда вы получаете неполноту как его следствие.
Как Тьюринг достиг этого? Я расскажу как он это сделал, потому что это трамплин для моей собственной работы. Способ, которым он это делал (и я уверен, вы слышали об этом) имеет отношение к тому, что называется Проблемой Остановки. Фактически, если вы обратитесь к работе Тьюринга 1936 года вы не найдете там слова "проблема остановки". Но суть этой проблемы, конечно же, там изложена.

Люди так же забывают, что Тьюринг говорил относительно "вычислимых чисел". Название этой его публикации: "On computable numbers, with an application to the Entscheidungsproblem" - "О вычислимых числах в приложении к проблеме разрешимости". Все помнят, что Проблема Остановки неразрешима и это следует из той самой работы, но не так много людей помнят, что Тьюринг там говорил относительно вычислимых действительных чисел. Моя работа так же имеет дело с вычислимыми и фатально невычислимыми действительными числами. Поэтому я хотел бы освежить в вашей памяти то, как выстроены аргументы Тьюринга.
Аргументы Тьюринга действительно уничтожают мечту Гильберта, и делается это простым способом. Метод Тьюринга основан только на диагональном процессе Кантора (для тех, кто знает, что это такое) приложенном к вычислению действительных чисел.
В том то и дело, что вся идея проста как дважды два, и она достаточно четко показывает, что мечта Гильберта, двух тысячелетняя кульминация развития того, что математики думали о математике, была неправильной. Работа Тьюринга - чрезвычайно глубока.
В чем суть аргументов Тьюринга?
Действительное число, как вы знаете, например 3.1415926..., является некой длинной, измеренной с произвольной точностью и имеет в своей записи бесконечное число цифр. И вычислимым вещественным числом, говорит Тьюринг, является такое число, для которого существует программа компьютера (или алгоритм) которая безостановочно вычисляет его цифры одну за другой. Например, имеется программа для числа pi и имеются алгоритм для решения алгебраических уравнений с коэффициентами в целых числах. На самом деле большинство действительных чисел, которые вы находите в анализе, вычислимы.
Однако они исключение, если вы знаете теорию множеств. Исключение, потому что мощность вычислимых действительных чисел счетное, в то время как мощность всех реальных чисел несчетно (вам не надо знать, что это означает). В этом суть идеи Тьюринга.
Идея состоит именно в этом. Вы составляете список из всех возможных компьютерных программ. Конечно, тогда еще не было никаких компьютерных программ, и Тьюринг был вынужден изобрести машину Тьюринга, которая оказалась огромным шагом вперед. Но теперь, зная, что такое программа, вы только говорите: представим себе воображаемый список, в котором занесена каждая возможная компьютерная программа.

P1 [Гедель 1931]
P2 [Тьюринг 1936]
P3
P4
P5
P6
.
.
.

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

P1 3.1415926... [Гедель 1931]
P2............. [Тьюринг 1936]
P3..........
P4.......
P5.....
P6...
.
.
.

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

P1 3.1415926...... [Гедель 1931]
P2................ [Тьюринг 1936]
P3................
P4................
P5
P6................
.
.
.

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

P1 -.d11_ d12 d13 d14 d15 d16 ... [Гедель 1931]
P2 -.d21 d22_ d23 d24 d25 d26 ... [Тьюринг 1936]
P3 -.d31 d32 d33_ d34 d35 d36 ...
P4 -.d41 d42 d43 d44_ d45 d46 ...
P5
P6 -.d61 d62 d63 d64 d65 d66_...
.
.
.

Прекрасно! Фактически, все эти цифры следуют за десятичной запятой. Так что первая цифра это первая цифра после десятичной запятой первого числа, вторая цифра - вторая цифра после десятичной запятой второго числа, третья - третьего числа, четвертая - четвертого, пятая - пятого. И это не важно, если пятая программа не производит пятую цифру. Это действительно не имеет значения. Поставьте на этом месте пробел и идите дальше.
Что вы делаете теперь? Вы изменяете эти цифры. Делаете их другими. Замените каждую цифру на диагонали и соберите эти измененные цифры в новое число с десятичной запятой впереди. Это будет новое действительное число.
То, что вы сейчас проделали - это и есть диагональный процесс (процедура) Кантора. В результате вы получили цифру, которая отличается от первой цифры первого числа, второй, второго, третьей, третьего, четвертой четвертого, пятой пятого… и вы собираете их в одно новое число.

P1 -.d11_ d12 d13 d14 d15 d16 ... [Гедель 1931]
P2 -.d21 d22_ d23 d24 d25 d26 ... [Тьюринг 1936]
P3 -.d31 d32 d33_ d34 d35 d36 ...
P4 -.d41 d42 d43 d44_ d45 d46 ...
P5
P6 -.d61 d62 d63 d64 d65 d66_...
.
.
.
~d11 ~d22 ~d33 ~d44 ~d55 ~d66...

Это новое число не может стоять на каком-то месте в нашем списке из-за способа, которым оно было получено. Поэтому это невычислимое действительное число. Как Тьюринг переходит отсюда к Проблеме Остановки? Очень просто. Только спросите себе, а почему это число невычислимое? Я только что объяснил, как можно получить это число и это объяснение вполне могло бы служить алгоритмом получения данного числа. Чтобы вычислить N-ую цифру данного числа надо взять N-ую программу компьютера (вы можете это сделать), вы ее запускаете и ждете пока, она выдаст N-ную цифру и увидев ее, вы изменяете ее на другую. Что же нам здесь может помешать? Это все выглядит очень легким!
Проблема начинается в случае, если N-ная компьютерная программа никогда не выдаст N-ной цифры. А вы сидите и ждете у моря погоды. Это и есть Проблема Остановки, которую вы не можете решить: будет ли N-нная программа производить N-ную цифру вычисляемого ею числа или нет? Вот как Тьюринг получил неразрешимость Проблемы Остановки. Если бы вы могли решить Проблему Остановки, тогда бы вы могли бы выяснить поместит ли N-ная программа на N-нное место N-ную цифру. И если бы вы могли делать это, тогда бы вы фактически могли бы выполнять диагональную процедуру Кантора и вычислить действительное число, которое должно отличаться от любого реально вычислимого числа. Вычислить невычислимое число. Это и есть аргумент Тьюринга.

Почему это разрушило мечту Гильберта? Что Тьюринг доказал? То, что нет никакого алгоритма, никакой механической процедуры, которая решит, выдаст ли N-ую цифру N-ная компьютерная программа когда-либо или нет. Таким образом, не может иметься никакого алгоритма, который решит, останавливается программа компьютера когда-либо или нет (вопрос об N-ной цифры произведенной в соответствии с N-ной программой - частный случай).
Отлично. То что Гильберт хотел, было формальной аксиоматической системой, из которой должна была получена вся математическая истина, ничего кроме математическая истины и именно вся математическая истина. Если бы Гильберт мог достигнуть своей цели, то это автоматически дало бы нам механическую процедуру, чтобы решить будет ли программа компьютера когда-либо останавливаться или нет.
Почему?
Вы всего лишь пробегаете все возможные доказательства пока вы, или находите доказательство, что программа останавливается, либо вы находите доказательство, что программа никогда не остановиться. Так, если бы мечта Гильберта о конечном наборе аксиом (из которых должна следовать вся математическая истина) была бы возможна, тогда пробегая все возможные доказательства, вы могли бы проверить какое из них правильное, и вы бы тогда были способны решить остановиться ли любая программа компьютера или нет. В принципе могли бы. Но вы этого не можете согласно простым аргументам Тьюринга, который является всего лишь вариантом диагонального процесса Кантора, примененным к вычислению действительных чисел.
Это крайне просто!
Геделево доказательство изощренное и трудное. Аргументы же Тьюринга настолько фундаментальны, настолько глубоки, что все кажется естественным и неизбежным.
Но, конечно, они опирались на результат Геделя.

Вот как бы только это доказать...

Правильно. Хватит воду в ступе толочь, пашли на Поляну поиграем ))

Интервью Васика Рахлика http://chessbase.com/newsdetail.asp?newsid=6382

Тему затронули интересную. Со своей стороны, могу порекомендовать фундаментальную, но совершенно подъемную, увлекательную и местами просто захватывающую книгу Ж.-Л. Лорьера "Системы искусственного интеллекта". Глава в ней "Игровые программы. Психологические аспекты" будет очень интересна шахматистам. Есть там и несколько протясающих (по крайней мере меня) задач. Если не полениться и прочитать хотя бы эту главу, то вопрос об ИИ в шахматных программах, написанных спациалистами по ИИ, по-моему, отпадает.
Для скачивания книги можно набрать в yandex-e строку "Лорьер Системы искусственного интеллекта djvu"
Приятного путешествия в мир ИИ.

А квантовое программирование сильно отличается от обычного?) То есть программирование на квантовых компьютерах.... Или такого вообще нет еще? Что-то читал у Турчина вроде, но давно и ничего не помню) Квантовое программирование как-то ближе к ИИ, чем обычное? Или это просто более быстрый калькулятор...