Вкратце так: машина Тьюринга обладает бесконечной лентой, в каждой ячейке ленты хранится какая-то буква алфавита.
Поэтому память машины Тьюринга бесконечна.
Есть программы для обычных компьютеров, имитирующие работу машины Тьюринга. Но данная имитация неполная, так как в машине Тьюринга присутствует абстрактная бесконечная лента. Бесконечную ленту с данными невозможно в полной мере имитировать на компьютере с конечной памятью: суммарная память компьютера — оперативная память, жёсткие диски, различные внешние носители данных, регистры и кэш процессора и др. — может быть очень большой, но тем не менее всегда конечна.
В случае машины Тьюринга с ограниченной памятью мы имеем фактически конечный автомат.
В нем правила перехода могут образовывать цикл — программа "зависает".
На практике это мало что дает, так как число состояний — очень много.
Что такое полное состояние?
Есть, скажем, у нас комьютер, у него N ячеек памяти по 8 бит каждая. Всего 8*N бит.
Первые P ячеек хранят байт-код программы, далее идет I ячеек которые хранят входные значения (аргументы) нашей программы.
Остальные ячейки инициализированны в 0 перед запуском программы. O из них будет представлять выходные результаты программы, а остальные ячейки — временные переменные.
У компьютера есть регистры, регистр IP, который 0 перед стартом,
и некоторое число регистров общего назначения — R0...R7, допустим,
R0 — еще и является регистром флагов (ну єто несущественные детали наверное).
P ячеек для байт кода | I ячеек для входных данных | O ячеек для результата | временные ячейки
всего N ячеек памяти + регистры R0...R7 и регистра IP.
Программа завершается, если регистр IP достигает значения P. Другой вариант — там ставится специальная инструкция — stop.
Полное состояние программы — это состояние всех ее N ячеек памяти и всех регистров, включая значения и регистра IP.
Допустим мы делаем эмулятор такой системы. Инициализируем ячеейки памяти, регистры. В первые P ячеек записали код программы для эмуляции.
Далее I ячеек — входные данные. Остальные — нули. Как и все регистры.
Это у нас первое состояние системы. Сохраним это состояние у себя в памяти, в списке посещенных состояний.
Выполняем первую инструктцию, которая хранится в байт коде по адресу в регистре IP (сейчас 0).
Некоторые регистры, и, возможно, ячейки памяти изменились. Имеем новое состояние нашей конечной машины.
Проверяем, есть ли у нас это состояние конечной машины в списке посещенных состояний.
Если есть — вуа-ля — наша конечная машина зависла.
Если нет, то добавляем текущее полное состояние нашей конечной машины в список посещенных состояний.
И продолжаем выполнять инструкции до тех пор, пока текущее полное состояние конечной машины не будет
найдено в списке посещенных состояний (зависли) либо регистр IP достиг значения P (закончили программу).
Если программа закончена — можно посмотреть на ее результат.
Число возможных состояний просто огромно — 2^(8*(N+ число_всех_регистров_включая_IP))
В чем идея полного состояния:
start:
n = n + 1;
goto start;
Ячейка n когда-нибудь переполнится, и значение n станет таким же как и раньше на той же строке программы (регистр IP такой же).
В случае 8-битных ячеек такое произойдет через 256 итераций цикла, 16-битных — 64к и так далее.
В случае более сложного алгоритма, когда программа использует две и более ячейки для хранения
числа, итоговый возврат к исходному состоянию произойдет, но гораздо позже, 2^24 для трехбайтовой переменной, 2^32 для четырехбайтовой переменной и т.д.
В реальной программа она может скакать по состояниям очень долго и замысловато, но смысл один —
если программа вошла в состояние в котором она раньше была — она зависла.
Из-за детерминированности. Если она вошла в состояние в котором раньше была — значит она через такое же число шагов вернется к нему снова.
То есть зависнет.
Тут надо еще понимать что у программы нет связи с "внешнем миром". То есть нет операций ввода-вывода,
когда пользователь по своей воле может ввести какие-то свои данные во время работы программы, типа std::cin >> a.
В случае если есть ввод пользователя — то такой анализ бессмыслен, так как поведение пользователя недетерминировано.
(помниться на меня как-то в 10-м классе школы снишло озарение и я сам для себя открыл детерминизм Лапласа,
несколько дней ходил ошарашенный, переосмысливая окрыжающий мир и рассказывая друзьям об этом;
через несколько лет в институте я узнал как это называется — "детерминизм Лапласа").
И еще надо различать полное состояние программы (всех ячеек памяти и регистров) от его каких-то частычных состояний (навроде состояния одной какой-то переменной).
Если просто будет:
start:
goto start;
То программа из одного полного состояния перейдет в это же полное состояние.
То есть цикл в графе полных состояний состоит из одного ребра, соединяющего между собой одну и ту же вершину.
Всего число полных состояний у конечной машины — 2^(8*(N+ число_всех_регистров_включая_IP)).
Поэтому самый возможный длинный цикл до обнаружения зависания (или до завершения программы) не будет превышать этого числа.
Правда это число очень велико.
Ну это я так. Ничего нового, просто пересказ моих старых соощений.
Теперь немного новых рассуждений (которые правда есть кристаллизация старых).
В чем особенность полной Машины Тьюринга?
В бесконечной памяти.
Это означает, что имея неограниченное число памяти, можно хранить неограниченные числа, без их переполнения.
(Число или переменную можно хранить в нескольких ячейках, или даже в неограниченном числе ячеек)
В таком случае цикл:
start:
n = n + 1;
goto start;
не вернется в свое предыдущее состояние (из-за переполнения), а будет двигаться в сторону бесконечности, порождая все новые и новые состояния.
Вот тут проблема. Однаружить такой зависание, очень сложно или вообще невозможно.
Алгоритм может быть нетривиальный, вычислять простые числа или еще что-то в таком духе.
Я хочу заметить вот что.
Такую машину Тьюринга с бесконечной лентой можно представить как вычислительную машину с конечным числом ячеек,
однако каждая ячейка будет иметь бесконечное число бит. То есть каждая ячейка может хранить неограниченное целое число.
По-моему это будет равнозначное определение.
Такая вот бесконечная машина (а это машина Тьюринга) может "зависнуть" двумя способами.
Машина Тьюринга может зависнуть циклически. Это означает, что хоть у машины Тьюринга неограниченный объем памяти,
из-за особенностей конкретного алгоритма (возможно из-за какой-то ошибки, переполнения, или просто label: goto label,
она войдет в одно из своих предыдущих состояний. Это даже можно теоритически детектировать такой случай.
Ведь изначально МТ использует только конечное число ячеек — другими словами — полное состояние МТ можно запоминать,
до тех пор пока не будет бесконечной аллокации (когда n = n + 1 в цикле).
Машина Тьюринга может зависуть ациклически. Это означает что МТ будет порождать все новые и новые состояния,
и число таких состояний будет бесконечно. Для классической МТ с лентой это означает, что головка движется
все время в одну сторону и пишет какие-то числа. Для традиционных програм — программа бесконечно аллоцирует память и пишет в нее.
Но традиционная программа, конечно, когда-нибудь завершится с ошибкой исчерпания памяти.
В случае МТ с конечным числом неограниченных ячеек (каждая ячеейка хранит любое целое число без переполнения) это будет примерно равнозначно циклу:
start:
n = n + 1;
goto start;
Эту же программу можно написать для МТ с лентой, при этом для хранения все большего числа потребуется большее число ячеек на ленте,
и программа будет бесконечно аллоцировать (писать) на бесконечную ленту.
Если МТ с бесконечной лентой мы может представить, как я писал выше, как вычислительную машину с конечным числом ячеек,
однако каждая ячейка будет иметь бесконечное число бит. То есть каждая ячейка может хранить неограниченное целое число.
Полное состояние МТ с конечным числом неограниченных ячеек мы может представить как точку в многомерном пространстве.
Пусть N — число ячеек МТ с конечным числом неограниченных ячеек.
Тогда точка в N-мерной пространстве есть полное состояне такой МТ.
МТ начинает свою работу в какой-то начальной точке.
На каждом шаге МТ изменяет свое полное состояние на новое.
Трактория движения точки в N-мерном просранстве есть траектория полного состояния МТ.
Если МТ приняла одно из своих предыдущих полных состояний — это зависание циклического типа.
Когда полное состояние МТ начнет "уходить в бесноченость" — то это зависание ациклического типа. Они наиболее сложные для понимания и правильного определения.
Я вот тут недавно повторял определение вещественных чисел при помощи рядов.
В частности теорию бесконечных десятичных дробей — вики.
Мне кажется (чисто гипотетически), что программы на МТ, которые зависают циклически соответствуют рациональным числам,
которые невозможно представить в виде десятичной дроби. Например, дробь 1\3 представляется в виде бесконечной десятичной дроби 0.333333...
Или 0.3(3). Из-за того что тройка повторяется циклически, это
означает, что гипотетический алгоритм, генерируюющий (вычисляющий) такую десятичную дробь — он как раз зависает циклически.
То есть входит в одно из своих предыдущих состояний, и из-за этого генерирует все время 3.
Замечу, что длина цикла зависания может быть больше, и дроби могут быть вида 0.5434(435573).
И наоборот, такие десятичные дроби соответствуют циклически зависающим алгоритмам на МТ.
Десятичные дроби, которые имеют конечное число цифр для своего представления соответствуют алгоритмам на МТ, которые завершают свою работу.
Например 1\2 = 0.5. Алгоритм на МТ завершается.
Десятичные дроби, которые соответствуют иррациональным числам, соответствуют алгоритмам на МТ, которые зависают ациклически.
Например, число Пи. Десятичные числа после запятой числа Пи никогда не повторяются и их бесконечное число.
Другой пример — синусы и косинусы и бесконечные ряды Тейлора (соответствующие алгоритмы на МТ, зависающие ациклически).
Еще мне кажется что есть связь между диофантовыми уравнениями и проблемы останова МТ.
Одно из известных уравнений (Великая теорtма Ферма) a^n + b^n = c^n — не имеет целых корней для n >= 3.
Эту задачу можно оформить в виде программы для МТ с конечным числом неограниченных ячеек, который просто
перебирает все целые значение a, b, c и n для n >= 3. И если решение находится, то программа завершает свою работу.
Если же программа зависает ациклически (а такая программа может зависнуть только ациклически) — значит целых решений не сущестуют.
Если бы существовал способ решения задачи останова для МТ (с безконечной лентой, или с конечным числом неограниченных ячеек),
то мы автоматически бы получили доказетельство теоремы Ферма.
Другими словами — решение задачи останова МТ — это доказательство того, что МТ остановится или нет, и каким способом.
Также решение задачи останова МТ означает доказательство или опровержение, например, abc-гипотезы.
Поэтому решить задачу останова МТ с бесконечной лентой — увы, либо невозможная задача, либо чрезвычайно сложная.
Получается, что задача останова МТ есть более общий случай решения всех диофантовых уравнений,
включая и доказетельство теоремы Ферма и возможное доказательство abc-гипотезы.
А общий случай доказывается сложнее чем частный. Доказательство abc-гипотезы уже 8 лет как проверяют,
так и не могут выяснить, и в мире только 10-20 человек в этом шарят — крайне архисложная вещь.
То проблема останова МТ — еще сложнее (если не невозможная задача).
Третий Рим должен пасть!
Re: Снова за старое: Машина Тьюринга пролема останова
Здравствуйте, GhostCoders, Вы писали:
GC>Поэтому решить задачу останова МТ с бесконечной лентой — увы, либо невозможная задача, либо чрезвычайно сложная. GC>Получается, что задача останова МТ есть более общий случай решения всех диофантовых уравнений, GC>включая и доказетельство теоремы Ферма и возможное доказательство abc-гипотезы.
Невозможность решения задачи останова МТ с бесконечной лентой доказана. Причем там какое-то довольно простое доказательство.
Re[2]: Снова за старое: Машина Тьюринга пролема останова
Здравствуйте, Pzz, Вы писали:
Pzz>Невозможность решения задачи останова МТ с бесконечной лентой доказана. Причем там какое-то довольно простое доказательство.
Это доказательство мне и двадцать лет назад казалось стремным, и в 2009 году и сейчас.
Возможно, существует другое доказательство, которое будет убедительным для меня.
Готов подискутировать по этому вопросу.
Рассмотрим множество S алгоритмов, которые принимают на вход натуральное число и на выходе тоже выдают натуральное число. Выберем какой-нибудь полный по Тьюрингу язык программирования. Каждый алгоритм можно записать в виде конечной последовательности символов на этом языке. Упорядочим множество S (это возможно, поскольку оно является множеством конечных последовательностей элементов конечного множества и потому счётно), при этом каждый алгоритм получит свой порядковый номер. Назовем Анализатором гипотетический алгоритм, который получает на вход пару натуральных чисел (N,X), и:
останавливается и возвращает 1, если алгоритм с номером N не останавливается, получив на вход X
не останавливается в противном случае (если алгоритм с номером N останавливается, получив на вход X).
Проблему остановки можно переформулировать следующим образом: существует ли Анализатор?
Теорема. Анализатор не существует.
Докажем это от противного. Допустим, Анализатор существует. Напишем алгоритм Диагонализатор, который принимает на вход число N, передает пару аргументов (N,N) Анализатору и возвращает результат его работы. Другими словами, Диагонализатор останавливается в том и только том случае, если не останавливается алгоритм с номером N, получив на вход число N. Пусть K — это порядковый номер Диагонализатора в множестве S. Запустим Диагонализатор, передав ему это число K. Диагонализатор остановится в том и только том случае, если алгоритм с номером K (то есть, он сам) не останавливается, получив на вход число K (какое мы ему и передали). Из этого противоречия следует, что наше предположение неверно: Анализатор не существует, что и требовалось доказать.
Программа — принимает на вход натуральное число Х и на выходе дает натуральное число.
Я понимаю, что диагонализатор тут нужен для того, чтобы анализатор анализировал сам себя.
Так как анализируемая программа принимает только один аргумент, то чтобы анализатор анализировал сам себя, нужен
некий "адаптер" в виде диагонализатора.
И еще предлагается, что анализатор остановится, если анализируемая программа зависнет, и наоборот, зависнет, если анализируемая программа остановится.
Возникает типа парадокса, противоречия, из которого делается вывод о несуществовании такого анализатора.
По мне это странный подход.
Первая претензия. Почему именно предполагается существование анализатора, который останавливается, когда
анализируемая программа зависает и наоборот? По моему это какое-то подыгрывание результату.
Почему бы, например, не предположить, что анализатор вернет 1 если анализируемая программа зависнет, и 0 — если остановится?
То есть анализатор никогда не зависнет. Тогда он сам для себя должен возвратить 0. В таком случае нет никакого противоречия.
И такой практический толк в анализаторе, предположенным Тьюрингом, который может сам зависнуть?
Вот запустили мы такой анализотор с какой-то программой и ждет результата.
Прождали день. Этот анализатор все еще работает и на второй день может вернуть 1, или же окночательно завис?
Только для доказательства того, что такой анализатор противоречив?
По моему, это "доказательство" лишь доказывает, что тот анализатор, допущенный Тьюррингом, именно в такой форме противоречив, а конкретно
имеет неопределенное поведение (undefined behaviour), не более.
Примерно, если объявить функцию на С:
bool some_func()
{
return !some_func();
}
А потом начать теоритизировать, что за значение вернет эта функция, и какие выводы из этого можно сделать.
В том виде анализатор, что предложил Тьюринг, имеет undefined behavour в зависимости от реализации самого анализатора.
Фактически, если анализатор как-то интерпретирует полученную программу, это фактически означает бесконечную рекурсию
D(X) -> A(X, X) ->интерпретация-> D(X) -> A(X, X) ...
И тут все implementation specific и зависит от того, какой анализатор первым найдет такую бесконечную рекурсию.
Четный или нечетный относительно самого первого вызова.
Если нечетный анализатор найдет зависание (считая, что первый анализатор имеет номер 1 в стеке вызовов), то вся цепочка вернет значение 1:
То есть, если мы хотели получить неопределенное поведение такого анализатора, то мы его получили. Не более.
Как я понял, это такой метод доказательства на несуществование чего-то.
Предполагают, что объект существует.
В случае существования такого объекта, логически вытекают какие-то определенные свойства для этого объекта.
Доказыватеся, что объект с такими свойствами противоречив, поэтому не существует.
Вот только в доказательстве Тьюринга ошибка.
Если анализатор существует, то совсем не обязательно такой анализатор должен иметь именно такие свойства, какими его наделяет Тьюринг.
А именно зависать, если программа останавливается, и останавливаться, если программа зависает.
И нет никаких оснований заявлять, что любые анализаторы, которые вообще могут сущствовать, будет обладать такими свойствами.
Вполне возможны анализаторы, которые возвращают либо 0 или 1.
Вот если бы Тьюринг показал, что если анализатор существует, то он обязательно должен зависать, если программа завершается, и наоборот,
то да, это было бы доказательство.
Вот к примеру, как Ферма доказал что корень из 2 — иррациональное число.
Для доказательства иррациональности sqrt(2) с использованием метода бесконечного спуска оно предполагается рациональным числом:
sqrt(2}= p / q
для некоторых натуральных чисел p и q. Тогда квадрат этого числа равен:
2 = p^2 / q^2
то есть
2*q^2 = p^2
Это означает, что p — чётное число. Для p=2*r
p^2 = (2*r)^2 = 4*r^2
при подстановке 4*r^2 вместо p^:
2*q^2 = 4*r^2
{\displaystyle 2q^{2}=4r^{2}}{\displaystyle 2q^{2}=4r^{2}}.
Деление на 2 обеих частей даёт: q^2=2*r^2, значит, q — также чётное число.
Таким образом, исходные числа p и q можно одновременно разделить на 2 и получить другое представление sqrt(2).
С полученными числами можно проделать ту же операцию, и так далее бесконечное число раз.
Таким образом строится бесконечно убывающая последовательность натуральных чисел, что невозможно.
То есть, sqrt(2) не является рациональным числом.
Вот это доказательство — пример правильного доказательства.
Здесь — если sqrt(2) — рациональное число, то отсуда следует строгие выводы:
что p — чётное число.
что q — тоже чётное число.
Если p и q — четные => строгий вывод о противоречии.
Пример если бы эту теорему доказывал "Тьюринг":
sqrt(2}= p / q
для некоторых натуральных чисел p и q.
Я хочу... (далее вставить любой бред), чтобы p и q были связаны уравнением p = q + 1 или еще что-то.
Тут смысл в том, что если предполагаемый объект существует, то это неизбежно ведет к логическому выводу о том,
что такой объект обязательно будет имеет свойства, которые ведут к противоречию.
Однако в случае доказательства Тьюринга, нет никаких оснований в том, что анализатор будет неизбежно
иметь такие свойства, какие хочет видеть Тьюринг (дурацкое предположение о том, что анализатор зависает, когда программа завершается и наоборот).
Здравствуйте, GhostCoders, Вы писали:
GC>Программа — принимает на вход натуральное число Х и на выходе дает натуральное число. GC>Я понимаю, что диагонализатор тут нужен для того, чтобы анализатор анализировал сам себя. GC>Так как анализируемая программа принимает только один аргумент, то чтобы анализатор анализировал сам себя, нужен GC>некий "адаптер" в виде диагонализатора.
Смысл доказательства в том, что какую бы сложную программу не умел анализировать анализатор, всегда можно сделать программу еще чуть сложнее. И показывается конкретный путь, как это сделать.
Это, кстати, напрямую связано с бесконечностью памяти. Если бы память была конечной, сложность программы тоже была бы конечной.
GC>По мне это странный подход. GC>Первая претензия. Почему именно предполагается существование анализатора, который останавливается, когда GC>анализируемая программа зависает и наоборот? По моему это какое-то подыгрывание результату.
Потому что по определению машины Тьюринга, валидная программа должна остановиться, чтобы выдать какой-то результат.
GC>Почему бы, например, не предположить, что анализатор вернет 1 если анализируемая программа зависнет, и 0 — если остановится? GC>То есть анализатор никогда не зависнет. Тогда он сам для себя должен возвратить 0. В таком случае нет никакого противоречия.
Чтобы что-то "вернуть", надо остановиться. Пока анализатор продолжает работать, он еще ничего не вернул.
GC>И такой практический толк в анализаторе, предположенным Тьюрингом, который может сам зависнуть?
Тьюринг отвечал на вопрос, "что такое алгоритм". Его ответ — "алгоритм, это программа для машины Тьюринга, которая останавливается после конечного числа шагов". Не каждая программа для машины Тьюринга является алгоритмом.
Следующих вопрос, какая задача является вычислительно разрешимой. Ответ — та, для которой может быть составлен алгоритм. И оказывается, что не всякая задача, которую можно сформулировать, является вычислительно разрешимой. Классический пример — проблема останова, программа, которая проанализирует другую программу и скажет, останавливается ли она.
GC>Вот запустили мы такой анализотор с какой-то программой и ждет результата. GC>Прождали день. Этот анализатор все еще работает и на второй день может вернуть 1, или же окночательно завис? GC>Только для доказательства того, что такой анализатор противоречив?
Да.
GC>По моему, это "доказательство" лишь доказывает, что тот анализатор, допущенный Тьюррингом, именно в такой форме противоречив, а конкретно GC>имеет неопределенное поведение (undefined behaviour), не более.
Это доказательство доказывает наличие алгоритмически неразрешимых задач.
Здравствуйте, Pzz, Вы писали:
Pzz>Смысл доказательства в том, что какую бы сложную программу не умел анализировать анализатор, всегда можно сделать программу еще чуть сложнее. И показывается конкретный путь, как это сделать.
Это лишь общие слова, которые максимум могут тянуть на гипотезу.
В доказательстве Тьюринга вообще-то элементарная логическая ошибка, странно что ее никто не заметил до меня.
И да, проясню свою позицию. То что в доказательстве Тьюринга ошибка, это автоматически не означает возможность создания анализатора.
Вопрос о создании анализатора становится открытым. Не ясно существует такой анализатор или нет.
GC>>Первая претензия. Почему именно предполагается существование анализатора, который останавливается, когда GC>>анализируемая программа зависает и наоборот? По моему это какое-то подыгрывание результату. Pzz>Потому что по определению машины Тьюринга, валидная программа должна остановиться, чтобы выдать какой-то результат.
Это-то понятно.
Однако сам Тьюринг допускает существование анализатора лишь в заранее невалидной форме —
который зависает, если анализируемая программа завершилась и выдала результат (см. доказательство Тьюринга).
GC>>Почему бы, например, не предположить, что анализатор вернет 1 если анализируемая программа зависнет, и 0 — если остановится? GC>>То есть анализатор никогда не зависнет. Тогда он сам для себя должен возвратить 0. В таком случае нет никакого противоречия. Pzz>Чтобы что-то "вернуть", надо остановиться. Пока анализатор продолжает работать, он еще ничего не вернул.
Вы опять ничего не поняли. Я предположил существование валидного анализатора, который всегда останавливается
и выдает результат в зависимости от анализа переданной программы:
1 — если анализируемая программа зависла
0 — если анализируемая программа завершилась (и вернула какое-то значение).
В такой форме анализатор должен вернуть 0 в случае если анализатор будет запущен для самомого себя.
По-моему вы никак не поймете суть моих претензий к доказательству Тьюринга о невозможности создания анализатора.
Тут весьма простая ошибка.
Для того чтобы вы лучше это поняли, я представлю вам ошибочное доказательство того,
что уравнение X — 3 = 5 не имеет решений.
"Уравнение X — 3 = 5 не имеет решений. Докажем это от обратного.
Допустим уравнение X — 3 = 5 имеет какое-то решение.
Скажем, что А — это решение уравнения и А <= 0 (А меньше или равно 0).
В таком случае, при максимально возможном значении А в 0 мы имеем:
0 — 3 = 5
-3 = 5
Очевидно, что -3 не равно 5, более того, -3 < 5.
Для значений А меньших 0, значение в левой части уравнения будет, очевидно, еще меньше, чем -3.
Следовательно, уравнение X — 3 = 5 не имеет решений."
Тут раздается возглас с задней парты и ученик спрашивает учителя:
"А для чего мы предположили что А меньше или равно 0? Только для доказательства того, что это уравнение не имеет решений?!"
"Да" — звучит невозмутимый ответ учителя.
Все остальные ученики в классе поворачивают головы назад и недовольно
смотрят на выскочку, который посмелил бросить тень на гениальное доказательство.
Вот таким-же приемом Тьюринг доказывает невозможность существования анализатора.
В случае уравнения, если мы сделали допущение, что А <= 0, и рассмотрели этот случай,
то мы должны рассмотреть случай, когда А > 0.
Мы же этого не сделали.
Тоже самое сделал и Тьюринг.
Фактически он допустил существование анализатора лишь в одной, ему выгодной форме.
И не рассмотрел другие варианты возможного существования анализатора.
Вот эти "странные" допущения Тьюринга:
Назовем Анализатором гипотетический алгоритм, который получает на вход пару натуральных чисел (N,X), и:
останавливается и возвращает 1, если алгоритм с номером {N не останавливается, получив на вход X
не останавливается в противном случае (если алгоритм с номером N останавливается, получив на вход X).
"Странное" тут в том, что Тьюринг допускает анализатор, который зависает сам.
И не рассматривает остальные варианты.
Другой (мой) вариант существования анализатора, это случай, когда анализатор всегда останавливается
и возвращает 1 или 0 в зависимости от того, зависла или нет анализируемая программа.
Это же просто и естественно (особенно для программистов), иметь анализатор,
который возвратит 1 или 0, типа функции is_halt(), которая принимает на вход некую программу.
Если переданная программа может потенциально зависнуть, то сам анализатор должен быть валиден и всегда останавливаться,
возращая 1 или 0.
Здравствуйте, GhostCoders, Вы писали:
GC>Это лишь общие слова, которые максимум могут тянуть на гипотезу. GC>В доказательстве Тьюринга вообще-то элементарная логическая ошибка, странно что ее никто не заметил до меня. GC>И да, проясню свою позицию. То что в доказательстве Тьюринга ошибка, это автоматически не означает возможность создания анализатора. GC>Вопрос о создании анализатора становится открытым. Не ясно существует такой анализатор или нет.
Слушай, ну если 100500 вполне серьезных математиков просмотрели это доказательство до тебя, и ошибок не нашли, вполне логично предположить, что ошибаешься где-то ты.
Здравствуйте, Pzz, Вы писали:
Pzz>Слушай, ну если 100500 вполне серьезных математиков просмотрели это доказательство до тебя, и ошибок не нашли, вполне логично предположить, что ошибаешься где-то ты.
Да, действительно, это логично, тут я соглашусь.
История знает случаи, когда доказанная теорема считалась доказанной многие годы, и с этим доказательством работали многие математики.
Однако по проишествии многих лет доказательство признавалось неверным.
Если возьмем за аксиому, что "Люди могут ошибаться", и аксиому "Тьюринг — человек", то отсюда следует, что "Тьюринг может ошибаться".
Если же взять за аксиому "Известные математики не ошибаются", и аксиому "Тьюринг — известный математик", то отсюда следует, что "Тьюринг не ошибается".
Здравствуйте, GhostCoders, Вы писали:
GC>"Странное" тут в том, что Тьюринг допускает анализатор, который зависает сам. GC>И не рассматривает остальные варианты.
GC>Другой (мой) вариант существования анализатора, это случай, когда анализатор всегда останавливается GC>и возвращает 1 или 0 в зависимости от того, зависла или нет анализируемая программа.
GC>Это же просто и естественно (особенно для программистов), иметь анализатор, GC>который возвратит 1 или 0, типа функции is_halt(), которая принимает на вход некую программу. GC>Если переданная программа может потенциально зависнуть, то сам анализатор должен быть валиден и всегда останавливаться, GC>возращая 1 или 0.
function Анализатор(N, X)
{
if (is_halt(N, X))
{
while (true) { }
}
else
{
return 1;
}
}
Да, уже нашел на английской википедии, функция g().
И получается, что типа Анализатор (is_halt) в таком случае становится "предсказателем" результата работы этой функции g().
(в смысле не возвращаемого значения, а результата зависнет-не зависнет).
И функция g() имеет все способы чтобы "нагадить" Анализатору, сделав все в точности наоборот, вместо зависания, что-нибудь вернуть,
или вместо успешного завершения зависнуть.
Типа человеку предсказали умереть через год, а он заключил пари с предстказателем, так вот этот человек, чтобы выиграть пари, специально прожил до ста лет.
Или наоборот. Предсказатель предсказал, что человек будет жить до 100 лет, а человек, заключил с ним пари, что предсказатель не прав,
и совершил самоубийство на следующий день, чтобы выиграть пари.
Хотя у меня останутся возражения, что, мол, Анализатор возвратил результат функции (зависла или нет)
для того гипотетического запуска (или запуска через интерпретацию) этой функции, который он сделал (или мог гипотетически сделать) сам,
а не того запуска, что запустил его самого.
То есть Тьюринг считает, что алгоритм должен работать строго детерминированно — как в функции в функциональных языках программирования,
а не императивных, с наличием глобальных переменных, и когда результат функции зависит от предыдыщих (разные всякие undefined behaviour)
вызовов. Проще говоря, Тьюринг не допускает дребезга результатов алгоритмов (типа как undefined behaviour).
Здравствуйте, GhostCoders, Вы писали:
GC>Хотя у меня останутся возражения, что, мол, Анализатор возвратил результат функции (зависла или нет) GC>для того гипотетического запуска (или запуска через интерпретацию) этой функции, который он сделал (или мог гипотетически сделать) сам, GC>а не того запуска, что запустил его самого.
GC>То есть Тьюринг считает, что алгоритм должен работать строго детерминированно — как в функции в функциональных языках программирования, GC>а не императивных, с наличием глобальных переменных, и когда результат функции зависит от предыдыщих (разные всякие undefined behaviour) GC>вызовов. Проще говоря, Тьюринг не допускает дребезга результатов алгоритмов (типа как undefined behaviour).
Да, это так. Занятие математикой требует каких-то идеализаций и абстракций.
[ . . . ]
— Вот мама даёт тебе, допустим, три яблока…
— Я скажу ей спасибо.
— Не перебивай меня, — сказал Малыш. — Если ты получишь три яблока от мамы, и два от папы, и два от Боссе, и три от Бетан, и одно от меня…
Докончить ему не удалось, потому что Карлсон погрозил ему пальцем.
— Так я и знал! — сказал он. — Я всегда знал, что ты самый жадный в семье, а это что-нибудь да значит!
— Подожди, сейчас не об этом речь, — сказал Малыш, но Карлсон упрямо продолжал:
— Вот если бы ты дал мне большой пакет, я быстро развернул бы его, а там кило яблок, и две груши, и горсть таких мелких жёлтых слив, знаешь?
— Перестань, — сказал Малыш. — Я же говорю про яблоки для примера, чтобы научить тебя сложению. Так вот, ты получил одно яблоко от мамы…
— Постой, — сердито закричал Карлсон. — я так не играю! А куда она дела те два яблока, которые только что собиралась мне дать?
Малыш вздохнул.
— Милый Карлсон, яблоки здесь ни при чём. Они нужны мне только для того, чтобы объяснить тебе, как надо складывать. Теперь ты понял, в чём дело?
Карлсон фыркнул.
— Думаешь, я не понимаю, в чём дело? Мама стащила у меня два яблока, как только я отвернулся.
— Перестань, Карлсон, — снова сказал Малыш. — Итак, если ты получишь три яблока от мамы…
Карлсон довольно кивнул.
— Ну вот видишь! Надо уметь за себя постоять, я всегда это знал. Я люблю порядок: что моё, то моё. Я получил три яблока от твоей мамы, два от папы, два от Боссе, три от Бетан и одно от тебя, потому что ты самый жадный…
— Да, так сколько же у тебя всего яблок? — спросил Малыш.
— А ты как думаешь?
— Я не думаю, я знаю, — твёрдо сказал Малыш.
— Ну тогда скажи! — попросил Карлсон.
— Нет, это ты должен сказать.
— Больно воображаешь! Скажи! Держу пари, что ты ошибёшься.
— Напрасно надеешься! — сказал Малыш. — У тебя будет одиннадцать яблок.
— Ты так думаешь? — переспросил Карлсон. — Вот и попал пальцем в небо. Потому что позавчера вечером я сорвал двадцать шесть яблок в одном саду в Лидингене, но потом я съел три штуки и ещё одно надкусил — ну, что ты теперь скажешь?
Малыш молчал, он просто не знал, что сказать. Но потом он вдруг сообразил.
— Ха-ха! Всё ты врёшь, — сказал он. — Потому что в июне ещё нет яблок на деревьях.
— Верно, нет, — согласился Карлсон. — Но тогда где вы-то их взяли, яблочные воришки!
Здравствуйте, GhostCoders, Вы писали:
Pzz>>Слушай, ну если 100500 вполне серьезных математиков просмотрели это доказательство до тебя, и ошибок не нашли, вполне логично предположить, что ошибаешься где-то ты. GC>Да, действительно, это логично, тут я соглашусь. GC>История знает случаи, когда доказанная теорема считалась доказанной многие годы, и с этим доказательством работали многие математики. GC>Однако по проишествии многих лет доказательство признавалось неверным.
Да, такие случаи бывали. Андре-Мари Ампер публиковал доказательство, что любая непрерывная функция дифференцируема почти всюду, и на него ссылались несколько раз. Почти сразу математики указали, что он использовал несколько неявных "очевидных" (но ложных) допущений. Первоначальные доказательства теоремы Эйлера для многогранников оказались неверными, потому что были найдены контрпримеры, которые показали, что люди расходятся в понимании, что такое многогранник, хотя никто до того момента не счёл нужным привести своё точное определение в доказательстве теоремы (см. Imre Lakatos, Proofs and Refutations).
Но после того, как в 20-м веке появились современные стандарты математической строгости, такие случаи почти не происходят. Или работа сразу отвергается за отсутствием строгости, или (для сложных теорем в узко специализированной области, в которой есть очень мало квалифицированных специалистов) ошибки находятся в течение нескольких лет (хотя сомнения обычно высказываются раньше). Большинство фундаментальных результатов (таких как теорема Тьюринга) доказаны-передоказаны многими способами, и многие из них уже имеют полностью формальные machine-checked proofs в нескольких различных формальных системах. Особо рассчитывать на скрытые ошибки в них я бы не советовал...
Здравствуйте, GhostCoders, Вы писали:
GC>И функция g() имеет все способы чтобы "нагадить" Анализатору, сделав все в точности наоборот, вместо зависания, что-нибудь вернуть, GC>или вместо успешного завершения зависнуть. GC>Типа человеку предсказали умереть через год, а он заключил пари с предстказателем, так вот этот человек, чтобы выиграть пари, специально прожил до ста лет. GC>Или наоборот. Предсказатель предсказал, что человек будет жить до 100 лет, а человек, заключил с ним пари, что предсказатель не прав, GC>и совершил самоубийство на следующий день, чтобы выиграть пари.
Не претендуя на точность и строгость, просто чтобы помочь интуиции, можно сказать, что доказательство Тьюринга использует примерно такой аргумент: ты не можешь правдиво ответить на вопрос «Верно ли, что ты ответишь на этот вопрос "нет"?».
Можно подумать, что проблема тут состоит в том, что вопрос ссылается сам на себя, и это, наверное, просто бессмысленная игра слов, которую невозможно формализовать и придать ей точный смысл. Однако, Гёдель и Тьюринг показали, что такие self-referential statements вполне поддаются формализации, надо лишь только выбрать способ, чтобы пронумеровать все утвеждения или алгоритмы (что Гёдель и сделал в своём доказательстве).
,
