Вы не вошли. Пожалуйста, войдите или зарегистрируйтесь.
Гостевая KasparovChess » Машинное отделение » Какое отношение имеют шахматные программы к искусственному интеллекту?
Чтобы отправить ответ, вы должны вход или регистрация
Интересно было бы узнать мнение программеров, интересующихся шахматистов и Хайдука)))
Если ли в шахматных программах реально хоть крупица ИИ, или это просто такие продвинутые калькуляторы?)
Отредактировано dan77790 (30/05/2010 11:13:53)
... и Хайдука
А что вы понимаете под ИИ?
1.Умение решать сложную интелектуальную задачу.
2.Самообучаемость.
3.Умение решать разнотипные интелектуальные задачи..
4.Исскуственная личность.
Мне кажется первое полностью отвечает понятию ИИ.
Мне больше второй пункт нравится)
Отредактировано dan77790 (30/05/2010 11:39:27)
Самообучаемость? В движках её нет хотя бы потому что им просто некогда учиться. Они должны всё время работать. А обучение в процессе требует огромных ресурсов для сбора статистики и обработки. Да ещё не эффективно. Для большего эффекта требуется движок по сложности разработки и ресурсоёмкости превосходящий собственно игровой. Возникает вопрос, а зачем? Если программисту легче всё сделать своими руками на базе тестов.
Отредактировано Фримен (30/05/2010 12:14:39)
Когда-то давно пытались дать определение ИИ. Сначала остановились на п.1. Но тут же появились программы, решающие сложные интеллектуальные задачи. Народ почесал репу и сказал: "Нет, это не ИИ". И стали придумывать новые определения. На каждое такое определение находился умелец, который писал программу, которая полностью подходила под новое определение ИИ.
В конце концов это всем надоело, и кто-то (не помню кто) дал "вечное" определение ИИ:
"Я не могу дать этому определение, но всегда узнаю его, когда увижу".
Может, и нет никакого ИИ?) да и естественного интеллекта)
или это просто такие продвинутые калькуляторы
Калькулятор достаточно интеллектуален, чтобы решать поставленные перед ним задачи.
Моё мнение - никакого.
При прочтении названия топика вспомнилась известная фраза советского математика Александра Кронрода: «Шахматы — дрозофила ИИ»
Даже в старых чесбейзовских оболочках Фрица есть опция "обучаемость".
Что же тогда говорить о программах, построенных с использованием "искусственных нейронных сетей"? SAL, Morph, Neurochess и другие обучаются во время игры. при этом некоторые способны научиться играть с нуля в любую игру где есть два соперника.
Интересная статья о Neurochess: http://satirist.org/learn-game/systems/neurochess.html
SAL http://satirist.org/learn-game/systems/sal.html
Morph http://satirist.org/learn-game/projects/morph.html
Morph играл в ICC: http://www.chessclub.com/activities/fin … dle=morph2 Но, похоже USCS потеряли интерес к развитию проекта.
Как бы там ни было... Уверен, что использование ИНН достаточно перспективное направление.
Отредактировано Schurick (30/05/2010 17:39:22)
При прочтении названия топика вспомнилась известная фраза советского математика Александра Кронрода: «Шахматы — дрозофила ИИ»
В 50-60-х годах так и было. И свою роль шахматы тогда сыграли.
Потом оказалось, что шахматы как задача слишком просты - решаются гораздо более примитивными методами, чем построение ИИ.
Простота шахмат обманчива.
Если бы биологи сконцентрировали свои усилия на выращивании дрозофил для забегов и продаж, а не для опытов, то генетика как наука не далеко бы ушла с тех пор. Но, по такому пути ушло программирование в шахматах...
Мне кажется, что факт слабой игры програм, основанных исключительно на использовании мат.моделей искусственных нейронных сетей не означает, что эти методы не используются в современных движках.
Напр., более продвинутые эвристические методы отбора ходов-кандидатов на начальном этапе расчёта вариантов определило преимущество Рыбки перед другими программами. Это ближе к "интеллектуальному", а не компьютерному подходу перебора всех вариантов. Когда-нибудь шахматные программы будут принимать решения в партии перебирая намного меньше вариантов.
Где-то проскакивала информация о том, что один из первых проектов в котором Васик Рахлих принимал участие как программист, имел целью имитацию (emulation) работы мозга. Не удивительно, что одной из долгосрочных задач для него является поиск путей передачи шахматных знаний от компьютера человеку.
Шахматная программа в качестве тренера. Не початый край для создания ИИ.
Значит так, какие бы эвристические методы не использовались это просто программа, и не стоит возвышать нейросети, они настолько просты, что это скорее не дрозофиллы а бактерии, и вообще до искусственного интеллекта лет 100 ещё, если он возможен, а к тому времени 3 мировая будет или ещё какая катастрофа и всем будет не до науки.
Отредактировано просроченый_кмс (30/05/2010 22:20:59)
Да, нейросети мне кажется имеют к ИИ примерно такое же отношение, как и шахматные проги)
а к тому времени 3 мировая будет или ещё какая катастрофа и всем будет не до науки.
а вот и правильный ответ 
Значит так, какие бы эвристические методы не использовались это просто программа, и не стоит возвышать нейросети, они настолько просты, что это скорее не дрозофиллы а бактерии, и вообще до искусственного интеллекта лет 100 ещё, если он возможен, а к тому времени 3 мировая будет или ещё какая катастрофа и всем будет не до науки.
Да, нейросети мне кажется имеют к ИИ примерно такое же отношение, как и шахматные проги)
Это сарказм или Вы на полном серьёзе делаете такие утверждения? Разве способность к обучению и обобщению, контекстуальной обработки информации, толерантность к ошибкам и др. не является признаком разума? Зачем учёные из разных стран работают над моделированием мозга в рамках Blue Brain Project , если ИНС так просты и не имеют отношения к ИИ?
А что вы понимаете под ИИ?
Под ИИ обычно понимается набор задач, которые плохо решаются существующими методами, но хорошо решаются человеком. Определение неформальное, скорее можно говорить о совокупности программ и личной точке зрения автора.
просроченый_кмс пишет:Значит так, какие бы эвристические методы не использовались это просто программа, и не стоит возвышать нейросети, они настолько просты, что это скорее не дрозофиллы а бактерии, и вообще до искусственного интеллекта лет 100 ещё, если он возможен, а к тому времени 3 мировая будет или ещё какая катастрофа и всем будет не до науки.
dan77790 пишет:Да, нейросети мне кажется имеют к ИИ примерно такое же отношение, как и шахматные проги)
Это сарказм или Вы на полном серьёзе делаете такие утверждения? Разве способность к обучению и обобщению, контекстуальной обработки информации, толерантность к ошибкам и др. не является признаком разума? Зачем учёные из разных стран работают над моделированием мозга в рамках Blue Brain Project , если ИНС так просты и не имеют отношения к ИИ?
Разве подбор коэффицентов, изменение их, и проверка на тестах, лучше ли эти коэффиценты или хуже имеет отношение к интеллекту?
Мне кажется это должны быть реально обучающиеся программы, читал что есть такая которая может выучить язык в процессе общения, чем больше с ней общаешься тем больше она выучит, ну вот если после этого она научится решать задачи после их словесного описания, т.е. создавать свои алгоритмы для решения любой задачи, это и будет искусственный интеллект, а нейросети для этого слишком просты это просто инструмент, нужно ещё что то с ними в пару или много чего.
Отредактировано просроченый_кмс (31/05/2010 14:25:53)
Вот я и вывел определение искусственного интеллекта - способность создавать алгоритмы для решения любой задачи.
Отредактировано просроченый_кмс (31/05/2010 14:24:21)
Мне больше нравится такое определение, уже не помню откуда:
Интеллект - это способность не решать, а ставить задачи.
Не согласен, ставить задачи надо тем кто живёт в физическом мире, а мы говорим о чистом интеллекте, этот уровень повыше, является следствием.
Ставит задачи физика, решает интеллект.
И давайте не углубляться на слудующие уровни, может когда нибудь интеллект и поставит задачу уничтожить землян как в терминаторе, но он уже будет интеллектом, поэтому считаю моё определение верным.
Вот я и вывел определение искусственного интеллекта - способность создавать алгоритмы для решения любой задачи.
Это алгоритмически неразрешимая задача.
Мне больше нравится такое определение, уже не помню откуда:
Интеллект - это способность не решать, а ставить задачи.
Задача постановки задачи это задача более высокого порядка 
просроченый_кмс пишет:Вот я и вывел определение искусственного интеллекта - способность создавать алгоритмы для решения любой задачи.
Это алгоритмически неразрешимая задача.
Не согласен, шахматные программы тоже научились играть как гроссмейстеры не сразу.
Вот так же и сначала надо создавать программы которые будут учиться делать простое, а потом создавать которые будут учиться думать более глубоко.
Пусть этот интеллект создаст хотя бы примитивный алгоритм, т.е. сначала надо создать такой интеллект, а потом уже люди поймут что к чему, разовьётся новое направление, и лет через надцать будут серьёзные успехи.
К тому же мы пример разрешимости такой задачи.
Отредактировано просроченый_кмс (31/05/2010 14:54:15)
WinPooh пишет:Мне больше нравится такое определение, уже не помню откуда:
Интеллект - это способность не решать, а ставить задачи.Задача постановки задачи это задача более высокого порядка
И для этого надо жить в физическом мире и иметь какие то потребности, пока интеллект заключён в компьютере у которого есть электричество, и всё остальное, потребность ставить задачи не возникает.
Это задача более высокого порядка лишь с точки зрения физики, с точки зрения интеллекта, выше чем способности решать любые задачи не может быть ничего.
Отредактировано просроченый_кмс (31/05/2010 14:56:22)
Mustitz пишет:просроченый_кмс пишет:Вот я и вывел определение искусственного интеллекта - способность создавать алгоритмы для решения любой задачи.
Это алгоритмически неразрешимая задача.
Не согласен, шахматные программы тоже научились играть как гроссмейстеры не сразу.
Вот так же и сначала надо создавать программы которые будут учиться делать простое, а потом создавать которые будут учиться думать более глубоко.Пусть этот интеллект создаст хотя бы примитивный алгоритм, т.е. сначала надо создать такой интеллект, а потом уже люди поймут что к чему, разовьётся новое направление, и лет через надцать будут серьёзные успехи.
У Вас определение общее, а вы рассматриваете его на частном примере. Нехорошо.
А смысл сказанного мною такой: ставим ИИ какую-нить алгоритмически неразрешимую задачу. Например, остановится ли когда-нить данная машина Тьюринга. Соответственно построить алгоритм решения этой задачи невозможно, потому что такого алгоритма не существует. Доказать алгоритмическую неразрешимость невозможно по этой же причине. Вот и получается, что в общем случае определение бессмысленно.
Если говорить конкретно о шахматах, то построить алгоритм, который бы играл оптимальным образом, раз плюнуть. Генератор таблиц Налимова это делает. Но для выполнения этого алгоритма пока недостаточно вычислительных ресурсов. Получается надо ограниченность ресурсов вводить в задачу. В этом случае задача получается конечной и ее можно решить простым перебором. Но, опять же, на ее решение в данное время недостаточно вычислительных ресурсов. И т. д. и т. п.
просроченый_кмс пишет:Mustitz пишет:Это алгоритмически неразрешимая задача.
Не согласен, шахматные программы тоже научились играть как гроссмейстеры не сразу.
Вот так же и сначала надо создавать программы которые будут учиться делать простое, а потом создавать которые будут учиться думать более глубоко.Пусть этот интеллект создаст хотя бы примитивный алгоритм, т.е. сначала надо создать такой интеллект, а потом уже люди поймут что к чему, разовьётся новое направление, и лет через надцать будут серьёзные успехи.
У Вас определение общее, а вы рассматриваете его на частном примере. Нехорошо.
А смысл сказанного мною такой: ставим ИИ какую-нить алгоритмически неразрешимую задачу. Например, остановится ли когда-нить данная машина Тьюринга. Соответственно построить алгоритм решения этой задачи невозможно, потому что такого алгоритма не существует. Доказать алгоритмическую неразрешимость невозможно по этой же причине. Вот и получается, что в общем случае определение бессмысленно.
Если говорить конкретно о шахматах, то построить алгоритм, который бы играл оптимальным образом, раз плюнуть. Генератор таблиц Налимова это делает. Но для выполнения этого алгоритма пока недостаточно вычислительных ресурсов. Получается надо ограниченность ресурсов вводить в задачу. В этом случае задача получается конечной и ее можно решить простым перебором. Но, опять же, на ее решение в данное время недостаточно вычислительных ресурсов. И т. д. и т. п.
Я говорю не о шахматах а о том что Москва не сразу строилась, от простого к сложному можно создать программу которая будет решать задачи.
"Например, остановится ли когда-нить данная машина Тьюринга." я даже не понял смысла вашей задачи, но если поставить искусственному интеллекту неразрешимую задачу он подумает и просто скажет вам об этом, неужели вы думаете интеллект не сможет общаться.
Ок новое определение дополненное: интеллект - способность создавать алгоритмы для решения любой задачи, а если задача алгоритмически не решается понимать это.
Отредактировано просроченый_кмс (31/05/2010 15:17:23)
"Например, остановится ли когда-нить данная машина Тьюринга." я даже не понял смысла вашей задачи, но если поставить искусственному интеллекту неразрешимую задачу он подумает и просто скажет вам об этом.
Засада именно в том, что подумает - но не скажет. И это доказано стоматологами математически, а не философскими рассуждениями.
кстати, имейте ввиду, что ИИ без электричества ноль! кончится электричество и все, пипец ИИ, накумекался
просроченый_кмс пишет:"Например, остановится ли когда-нить данная машина Тьюринга." я даже не понял смысла вашей задачи, но если поставить искусственному интеллекту неразрешимую задачу он подумает и просто скажет вам об этом.
Засада именно в том, что подумает - но не скажет. И это доказано
стоматологамиматематически, а не философскими рассуждениями.
Я могу сказать лишь то, что подумав на каким то алгоритмом прогрмамма выдаст либо однозначный ответ что он остановится, либо что не знает, и сама придумает проблему остановки и то доказательство которое приведено в википедии.
Приведите мне хоть 1 пример программы по которой нельзя понять остановится она или нет.
К тому же всё это было сформулировано когда понятия искусственный интеллект не существовало, т.е. самая главная проблема в самообучаемости и самоусложнения программ ИИ, 70 лет назад об этом даже не думали.
Так что запнувшись над решением "остановится ли когда-нить данная машина Тьюринга" ИИ подумает придумает более сложный алгоритм проверки, и за конечное время решит проблему.
Отредактировано просроченый_кмс (31/05/2010 15:41:27)
Я могу сказать лишь то, что подумав на каким то алгоритмом прогрмамма выдаст либо однозначный ответ что он остановится, либо что не знает
Задача остановиться и сказать "не знаю" - тоже попадает в область проблемы остановки.
К тому же всё это было сформулировано когда понятия искусственный интеллект не существовало
Истинность математического доказательства не зависит от того, были ли сформулированы какие-то новые понятия. Теорема или доказана, или нет. Эта - доказана.
Приведите мне хоть 1 пример программы по которой нельзя понять остановится она или нет.
Вот неплохой кандидат:
http://www.ega-math.narod.ru/Nquant/Collatz.htm
http://ru.wikipedia.org/wiki/%D0%9F%D1% … 0%BA%D0%B8
В теории вычислимости проблема остановки — это проблема разрешимости, которая может неформально быть поставлена в виде:
Даны описание алгоритма и его начальные входные данные, требуется определить, сможет ли выполнение алгоритма с этими данными завершиться когда-либо. Альтернативой этому является то, что он работает всё время без остановки.
Алан Тьюринг доказал в 1936 году, что общий алгоритм для решения проблемы остановки для любых возможных входных данных не может существовать. Мы можем сказать, что проблема остановки неразрешима на машине Тьюринга.
Петр Новиков в 1955 г. показал, что проблема остановки почти наверняка эквивалентна так называемой "проблеме тождества слов" в теории групп и компьютерной лингвистике.[источник не указан 131 день]
[править] Набросок доказательстваРассмотрим множество S алгоритмов, которые принимают на вход натуральное число и на выходе тоже выдают натуральное число. Выберем какой-нибудь полный по Тьюрингу язык программирования. Каждый алгоритм можно записать в виде конечной последовательности символов на этом языке. Упорядочим множество S лексикографически (в словарном порядке), при этом каждый алгоритм получит свой порядковый номер. Назовем Анализатором гипотетический алгоритм, который получает на вход пару натуральных чисел (N,X), и:
* останавливается и возвращает 1, если алгоритм с номером N не останавливается, получив на вход X
* не останавливается в противном случае (если алгоритм с номером N останавливается, получив на вход X).Проблему остановки можно переформулировать следующим образом: существует ли Анализатор?
Теорема. Анализатор не существует.
Докажем это от противного. Допустим, Анализатор существует. Напишем алгоритм Диагонализатор, который принимает на вход число N, передает пару аргументов (N,N) Анализатору и возвращает результат его работы. Другими словами, Диагонализатор останавливается в том и только том случае, если не остановливается алгоритм с номером N, получив на вход число N. Пусть K - это порядковый номер Диагонализатора в множестве S. Запустим Диагонализатор, передав ему это число K. Диагонализатор остановится в том и только том случае, если алгоритм с номером K (то есть, он сам) не останавливается, получив на вход число K (какое мы ему и передали). Из этого противоречия следует, что наше предположение неверно: Анализатор не существует, что и требовалось доказать.
=========================================
Попытавшись понять смысл всего этого, всё таки иногда писал программки, там и не такое приходится понимать, скажу а Почему это условием этого Анализатора должно быть то что "не останавливается в противном случае (если алгоритм с номером N останавливается, получив на вход X)."
т.е. нам по ходу теории навязывают логическое противоречие из области - "я говорю неправду".
"не останавливается в противном случае (если алгоритм с номером N останавливается, получив на вход X)." как они определят что он не останавливается подождут бесконечность лет? видно что даже если её принять - теория неработоспособна.
Дело анализатора выдавать либо 1 либо 0, если он будет это делать соответственно останавливаться и выдавать результат, то весь остальной бред насчёт диагонализатора и вообще всё это можно выкинуть на свалку.
З.Ы. Где можно высказать свою претензию по поводу этого условия? интересно послушать мнение математиков, ведь оно не является необходимым свойством анализатора.
Отредактировано просроченый_кмс (31/05/2010 16:14:12)
как они определят что он не останавливается
for (int x = 0; x < 10; x = x + 0) {}
Как Вы думаете, этот цикл завершается? Нужно ли Вам для того, чтобы это определить, бесконечное количество лет?
"Навязывание логического противоречия" - это обычный метод доказательства от противного. Мне он впервые встретился в учебнике геометрии для 6-го класса.
А теперь другой цикл:
while (N != 1)
{
if ((N % 2) == 0)
N = N / 2;
else
N = 3 * N + 1;
}
Требуется написать программу, которой на вход дают число N, а она определяет - завершится этот цикл, или нет.
просроченый_кмс пишет:как они определят что он не останавливается
for (int x = 0; x < 10; x = x + 0) {}
Как Вы думаете, этот цикл завершается? Нужно ли Вам для того, чтобы это определить, бесконечное количество лет?"Навязывание логического противоречия" - это обычный метод доказательства от противного. Мне он впервые встретился в учебнике геометрии для 6-го класса.
1й вопрос. Речь об анализаторе, проблема в том что в самой теории указано что если анализатор определил что программа останавливается, он не останавливается, это и есть результат его работы, как они это определят.
2й вопрос. Логическое противоречие либо есть либо нет, а тут создание искусственного условия этому анализатору, без этого условия "не останавливается в противном случае (если алгоритм с номером N останавливается, получив на вход X)." он будет прекрасно работать, выдавая 1 или 0?
В том смысле что тут придумали противоречие а потом создали условия в теории под него, с таким же успехом можно утверждать что 2+2=5
Сначала прочитайте что я писал а потом утверждайте.
Отредактировано просроченый_кмс (31/05/2010 16:26:11)
Я так понял, что доказательство Петра Новикова от 1955 года как раз устанавливает эквивалентность двух разных Анализаторов (один - который выдаёт 1 или 0, а другой - выдаёт 1 или не останавливается).
Я так понял, что доказательство Петра Новикова от 1955 года как раз устанавливает эквивалентность двух разных Анализаторов (один - который выдаёт 1 или 0, а другой - выдаёт 1 или не останавливается).
Интересно, вот это уже по делу, тут надо подумать)
Но фраза, не вдохновляет это уже не жёсткое доказательство - Петр Новиков в 1955 г. показал, что проблема остановки почти наверняка эквивалентна так называемой "проблеме тождества слов" в теории групп и компьютерной лингвистике.[источник не указан 131 день]
И без ссылки вообще непонятно о чём речь.
Отредактировано просроченый_кмс (31/05/2010 16:30:32)
З.Ы. Где можно высказать свою претензию по поводу этого условия? интересно послушать мнение математиков, ведь оно не является необходимым свойством анализатора.
Это просто более слабое условие (которые так любят математики), чем выдача 0 или 1. Очевидно, что если у нас есть программа, которая выдает 0 или 1, то мы из нее легко можем построить требуемую в условии машину Тьюринга: если мы пришли к выводу, что надо вернуть 0, то мы зацикливаем машину. Обратное, вообще говоря, неверно.
Соответственно, если теорема справедлива, то не существует указанной машины Тьюринга, и, как следствие, не существует машина Тьюринга, которая бы выдавала 0 или 1, как хочешь ты.
Другими словами, Диагонализатор останавливается в том и только том случае, если не остановливается алгоритм с номером N, получив на вход число N. Пусть K - это порядковый номер Диагонализатора в множестве S. Запустим Диагонализатор, передав ему это число K. Диагонализатор остановится в том и только том случае, если алгоритм с номером K (то есть, он сам) не останавливается, получив на вход число K (какое мы ему и передали)
Давайте подумаем.
Т.е. Диагонолизатор не сможет остановиться потому что Анализатор зациклится посчитав Диагонализатор конечной программой, а это противоречие.
НО
Проблема в том что тут подменяют понятия, т.к. изначально Диагонализатор конечная программа, но из за того что Анализатор зацикливается и приходится ждать вечность ответа от него, делается вывод что диагонализатор не конечная программа, а это противоречие.
Т.е. получается что если программа остановилась по каким то внешним причинам она сразу становится бесконечной, не согласен, если я вырублю комп когда он будет думать до 30 полуходов это не значит что это бесконечная программа из за невозможности её физического завершения.
Получается что любая программа ждущая данных и если ей их не дают считается незавершимой никогда, это неправильно, получается программа даже из одной строчки никогда не завершится, а это уже не из области программирования, так что это доказательство туфта, по нему получается что любая простейшая программа может никогда не завершиться а может и завершиться, всё зависит не от логики а от того вставлена ли вилка в розетку, к примеру.
Т.е. Диганолизатор простейшая прогрмамма из за этого вдруг оказывается бесконечной, надеюсь бесмысленность этого понятна.
Отредактировано просроченый_кмс (31/05/2010 16:57:59)
Получается что любая программа ждущая данных...
Эти теоремы сформулированы для машины Тьюринга. Модель этой машины не предусматривает операции ввода данных. Считается, что все исходные данные уже есть на ленте в момент старта программы.
просроченый_кмс пишет:Получается что любая программа ждущая данных...
Эти теоремы сформулированы для машины Тьюринга. Модель этой машины не предусматривает операции ввода данных. Считается, что все исходные данные уже есть на ленте в момент старта программы.
Ок есть, но, всё равно, анализатор посчитал диагонализатор конечной программой, но мы внешние наблюдатели этого не можем понять потому что диагонализатор никогда не выдаст нам ответ про себя, да и про некоторые другие программы, но это не означает что он бесконечен из за нашего незнания, получается бесконечным не сам диагонализатор, а вся программа записанная в машине этого тьюринга в данный момент т.е. диагонализатор+зацикленный анализатор, а это уже не сам диагонализатор по которому строится это противоречие.
Отредактировано просроченый_кмс (31/05/2010 17:13:02)
Небольшая непонятка, не совсем понимаю почему нужно передавать именно(N,N) а не любое число (N,5) главное ведь что бы анализатор анализировал диагонализатор.
На 100% не скажу, но есть подозрение, что в доказательстве применяется так называемый диагональный метод Кантора. Проще всего его иллюстрирует доказательство несчётности действительных чисел.
http://en.wikipedia.org/wiki/Diagonal_method
В общих чертах, мы нумеруем какие-то объекты (числа, или алгоритмы), потом выписываем их один под другим, а потом из диагонали строим ещё один объект - который не совпадает ни с одним из уже имеющихся. Видимо, в доказательстве неразрешимости проблемы остановки используется как раз построение алгоритма по этой процедуре.
Точнее выразиться не могу
Не знаю что там в доказательстве, но по факту за работу диагонализатора со стороны человека который доказывает эту теорию, принимается работа диагонализатор+зацикленный анализатор, этого уже достаточно что бы отбросить эту теорию.
Отредактировано просроченый_кмс (31/05/2010 17:32:54)
Видимо, в доказательстве неразрешимости проблемы остановки используется как раз построение алгоритма по этой процедуре.
Точнее выразиться не могу
Нет, там все проще. Допустим есть алгоритм, которые в состоянии решить указанную проблему. Если на вход этого алгоритма поместить его же, то мы получим противоречие.
WinPooh пишет:Видимо, в доказательстве неразрешимости проблемы остановки используется как раз построение алгоритма по этой процедуре.
Точнее выразиться не могу
Нет, там все проще. Допустим есть алгоритм, которые в состоянии решить указанную проблему. Если на вход этого алгоритма поместить его же, то мы получим противоречие.
Почему это противоречие, алгоритм скажет что он сам конечен, или бесконечен, если туда добавили бесконечный цикл например, и всё.
Отредактировано просроченый_кмс (31/05/2010 17:48:45)
http://ric.uni-altai.ru/Fundamental/teo … pr15-4.htm
Проблема остановки для машины Тьюринга
Проблема остановки состоит в следующем: по машине T и произвольному слову B узнать, применима машина T к слову B или нет, другими словами, построить машину Тьюринга, которая была бы применима ко всем словам вида Ged(T)a0B, и в случае, если машина T применима к слову B, в заключительной конфигурации в клетке находился бы символ "1", а в остальных клетках - любые символы; если же машина T неприменима к слову B, то в заключительной конфигурации в клетке находился бы символ "0", а в остальных клетках - любые символы.
Предложение.
Проблема остановки алгоритмически неразрешима, т.е. не существует машины Тьюринга, решающей эту проблему в указанном смысле.
Доказательство [Мощенский,1973,c.141-142].
Пусть существует машина P, решающая проблему остановки. Пусть T - некоторая машина Тьюринга. Тогда P должна быть применима ко всем словам, вида Ged(T)a0B и, в частности, когда B=Ged(T), т.е. машина P должна быть применима к слову Ged(T)a0Ged(T). Машина P при работе над словом Ged(T)a0Ged(T) остановится в конфигурации ...<q1,1>..., если T применима к Ged(T) (т.е. когда T несамоприменима). Но машина, решающая проблему самоприменимости, начинает работать при слове Ged(T) на ленте. Поэтому, чтобы из машины P получить машину, решающую проблему самоприменимости, используем машину T2 (будем считать, что a есть "*", а b есть "1"), которая по этому соглашению любое слово B в алфавите {*,1} преобразует в слово Ba0B.
Теперь машина, решающая проблему самоприменимости, получается из машины T2 и P: сначала работает машина T2, а затем - машина P. Но это противоречит Предложению об алгоритмической неразрешимости проблемы самоприменимости. Следовательно, машина Тьюринга P не существует.
Предложение доказано.
Тут всё более туманно и не про алгоритмы которые конечные или нет а про некие слова, поэтому это я опровергнуть не смогу, не совсем понятно даже что такое применимость.
Отредактировано просроченый_кмс (31/05/2010 17:46:07)
Если алгоритм остановится и скажет, "Я не останавливаюсь" - это будет ложью.
Тут всё более туманно и не про алгоритмы которые конечные или нет а про некие слова
Под словом тут просто понимается (длинная-предлинная) запись алгоритма в виде нулей и единиц, например. Или номер нашего алгоритма в некотором гипотетическом Списке Всех Алгоритмов Длины N. Что то же самое.
Применимость - синоним останавливаемости. Т.е. машина A применима к слову B, если при запуске её с начальным состоянием ленты, равным B, машина A остановится.
Если алгоритм остановится и скажет, "Я не останавливаюсь" - это будет ложью.
Из того что я понял по википедии, наверно всё это приведено более понятным языком чем в 1973 году с их лентами, диагонализатор остановится только потому что зациклится анализатор, но это по моему мнению не означает что диагонализатор бесконечен.
Отредактировано просроченый_кмс (31/05/2010 17:52:58)
Почему это противоречие, алгоритм скажет что он сам конечен, или бесконечен, если туда добавили бесконечный цикл например, и всё.
Это все частности, которые не имеют к проблеме никакого отношения. Можно сделать алгоритм, который будет отвечать на поставленный вопрос для некоторого класса алгоритмов. Но нельзя написать алгоритм, который бы это делал для всех существующих алгоритмов.
Доказательство такое: итак, алгоритм обладает такими свойствами: останавливается, если аргумент зацикливается. Зацикливается, если аргумент останавливается.
Итак, этому алгоритму пускаем в качестве аргумента сам себя. И тут возникает противоречие. В нашем случае оба алгоритма суть одно и то же. Соответственно либо они оба остановятся, либо оба зациклятся (потому что вычисление одно и то же). Но сам алгоритм сформулирован так, что это противоречие, так как в случае остановки одного алгоритма, второй должен зацикливаться.
Исходя из этого получаем, что такой алгоритм не существует. Т. е. сколько бы мы в него эвристик не напихали, всегда найдется такой алгоритм, что он не сможет установить зацикливание (например, на самом себе).
Браво, Mustitz!
Получился парадокс лжеца в классическом виде
Парадоксы дедуктивной логики
http://ravil.astersoft.net/Students/AI/paradox.htm
Чтобы отправить ответ, вы должны вход или регистрация
[ Сгенерировано за 0,104 секунд(ы), выполнено 8 запросов ]
