Человеческая вычислительная мощь: могут ли люди решить проблему остановки на машинах Тьюринга?

60

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

Примечание : Очевидно, что в самом строгом смысле вы всегда можете сказать «нет», потому что есть машины Тьюринга, настолько большие, что их невозможно прочитать даже в течение жизни одного человека. Но это бессмысленное ограничение, которое не способствует актуальному вопросу. Таким образом, чтобы сделать вещи даже, мы должны были бы предположить людей с произвольной продолжительностью жизни.

Таким образом, мы могли бы спросить: учитывая машину Тьюринга T, представленную любым подходящим образом, произвольно долгоживущего человека H и произвольное количество буфера (т.е. бумаги + ручки), может ли H решить, останавливается ли T в пустом слове?


Следствие: Если ответ «да», разве это не решится, если у какого-нибудь компьютера есть шанс пройти тест Тьюринга?

битовая
источник
15
Люди могут понять, останавливаются ли некоторые конкретные машины. Но из-за неразрешимости проблемы остановки и тезиса Черча-Тьюринга нет алгоритмической процедуры, которую человек мог бы использовать для решения проблемы.
Карл Маммерт
6
@CarlMummert: у людей есть изобретательность; Эта изобретательность не обязательно связана с тем, что вы можете выразить в терминах ТМ. Причина, по которой hp неразрешима для TM, связана с противоречием в диагональном языке.
битовая
4
Если бы у людей была какая-то сила, чтобы выяснить, на каких входах останавливается данная машина Тьюринга, они, вероятно, не почувствовали бы необходимость сформулировать определение машины Тьюринга или классов P и NP и т. Д., Как они это сделали бы. в основном нам кажутся любопытством для описания совершенно тривиальных проблем. (Конечно, если у вас щедрое настроение, это можно рассматривать как описание наших отношений с детерминированными конечными автоматами.)
Ниль де Бёдрап,
6
@NieldeBeaudrap: я не согласен. Хотя мы могли бы на что-то быть способны, это все же может быть сложной задачей (избегать слова «трудно»). Кроме того, если мы не концентрируемся должным образом, мы склонны делать небрежные ошибки, особенно при утомительных заданиях.
битовая
8
Я думаю, что лучший и единственный ответ на ваш вопрос - никто не знает. Никто не знает, верен ли тезис Черча-Тьюринга или какие существуют ограничения на то, что люди могут вычислить. Мы можем сказать , что если человек может решить эту проблему , останавливая, они делают что - то , что машины Тьюринга не может.
Patrick87

Ответы:

28

Очень трудно определить человеческий разум с такой математической строгостью, какой возможно определить машину Тьюринга. У нас до сих пор нет работающей модели мышиного мозга, но у нас есть аппаратное обеспечение, способное его моделировать. У мыши около 4 миллионов нейронов в коре головного мозга. У человека 80-120 миллиардов нейронов (19-23 миллиарда неокортикальных). Таким образом, вы можете представить, сколько еще нужно провести исследований, чтобы получить работающую модель человеческого разума.

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

После принятия пропозиционального, а затем исчисления предикатов я спросил своего профессора логики:
«Есть ли какая-либо логика, которая может определить весь набор человеческого языка?»
Он сказал:
«Как бы вы определили следующее?
Чтобы увидеть Мир в песчинке
И Небеса в полевом цветке,
Держите Бесконечность на ладони своей
И Вечность через час.
Если вы сможете это сделать, вы будете прославиться."

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

Пока мы не поймем больше, вы можете найти некоторые идеи в области философии. Тем не менее, ни один ответ на ваш вопрос не является общепринятым.

http://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorems#Minds_and_machines http://en.wikipedia.org/wiki/Mechanism_(philosophy)#G.C3.B6delian_arguments

Давид Натингга
источник
Предполагая, что мозг можно смоделировать как совокупность молекул, взаимодействующих друг с другом, разве не будет достаточно доказать, что молекулы «вычислимы»? Кажется, есть некоторые доказательства этого предположения (см. OpenWorm).
Оливье Лалонд
@OlivierLalonde Ваше предположение подразумевает, что люди могут моделироваться с помощью машины Тьюринга и поэтому не могут решить проблему остановки. Тем не менее, ваше предположение слишком сильно. По принципу неопределенности en.wikipedia.org/wiki/Unterminty_principle в квантовой механике, состояние физической системы не может быть смоделировано на компьютере, так как любая случайная последовательность состояний не вычислима. Затем вы можете утверждать, что модель физической системы является детерминированной, а не простой. Вопрос сводится к тому, можно ли вычислить моделирование мозга.
Давид Натингга
@DavidToth Случайная бесконечная последовательность состояний не вычислима. Любая система, содержащая конечное число событий, является вычислимой, предполагая, что все величины в этой системе вычислимы по отношению друг к другу. И даже если это не так, мы бы просто получили ошибку округления, меньшую, чем тепловой шум, который не должен оказывать существенного влияния на познание человека. (На самом деле ошибка обязательно будет неизмеримо мала.)
Keen
@Cory Да, любое конечное подмножество любого набора, даже неисчислимого, вычислимо, но смысл в том, чтобы «имитировать будущее», а не воспроизводить прошлое. В этом смысле может не существовать машины Тьюринга, которая могла бы предсказать действия человека в произвольно отдаленном времени в будущем. Это должно было бы предсказать одну из комбинаций бесконечной последовательности будущих событий. Тот факт, что число возможных событий за один раз может быть конечным, не меняет неисчислимость бесконечной последовательности.
Давид Натингга
2
@ DavidToth Я не утверждаю, что вся реальность обязательно вычислима по Тьюрингу. Однако аргумент от квантовой случайности не выдерживает критики. Квантовая механика - это система, используемая физиками для вычисления свойств будущих состояний реальности. Физические (вычислимые) модели могут обрабатывать эту случайность, потому что число (различимых) результатов всегда исчисляемо (и, следовательно, вычислимо), даже в тех случаях, когда оно бесконечно. Обратите внимание, что также нет оснований полагать, что квантовая случайность даст людям, а не другим машинам, возможность оценивать неисчислимые функции.
Кин
16

Я думаю, что нет никакого способа дать однозначный ответ на этот вопрос, поскольку никто действительно не знает способностей человеческого разума (и я сомневаюсь, что кто-нибудь когда-либо узнает).

Но есть точка зрения, которая дает одно возможное решение или объяснение этого вопроса:

Когда мы ищем оракула, чтобы решить проблему остановки (или решить вопрос о доказуемости логических формул первого порядка и т. Д.), Мы, естественно, хотим, чтобы оракул был правильным , он не должен совершать ошибок. Но человеческий разум не соответствуетошибается. Никто не может честно сказать, что все заявления, которые он считает истинными, действительно верны. Это несоответствие можно рассматривать как источник силы, которую имеет человеческий разум. Из-за его непоследовательности он не является предметом ограничений, вытекающих из проблемы остановки, теоремы Гёделя о неполноте и т. Д. Мы допускаем ошибки, ошибочно верим в ложные утверждения и по мере роста наших знаний исправляем их (и, конечно, находим новые ложные утверждения, в которые мы верим). С другой стороны, мы хотим, чтобы все формализации понятия алгоритма или всех логических исчислений были последовательными, чтобы мы могли раз и навсегда доказать, что они свободны от таких ошибок. И это делает их ограниченными.

Петр Пудлак
источник
Мы не совершаем больше ошибок, чем наши системы доказательств. Это довольно распространено в работах по гипотезам, даже в математике. Иногда они приводят к результатам, которые доказуемо неверны (или обсервационно неверны в естественных науках), и мы пересматриваем наши убеждения и некоторые из наших рабочих гипотез. В математике это является основанием для доказательства путем сокращения до абсурда (которые не являются конструктивными). Недетерминированные автоматы также полагаются на идею, что можно получить результаты даже при исследовании неправильных путей, если можно также изучить другой путь. Там нет ничего, что отличало бы человеческий разум.
Бабу
Интересный момент о том, что несоответствие является одним из источников вычислительной силы ума. Тебе не приходило в голову, что могут быть и другие типы мышления, помимо математики, когда два явно противоречивых данных могут быть правдой? Качество «истины» как относительного понятия, которому нельзя присвоить число, является различием человеческой мысли, которую трудно (смею сказать, невозможно?) Полностью воспроизвести в машине. Суть в том, что определение психической несогласованности как «ошибочной веры в ложь» (как вы, похоже, делаете здесь) само по себе является довольно ограниченным кругозором.
Wildcard
Можно показать, что никто не может доказать, что сам никогда не ошибется, но это не значит, что они могут опровергнуть, они никогда не совершат ошибку. Например, предположим, что наша вселенная - это симулятор жизни Конвея, который не следует теории многих миров. Кроме того, предположим, вы заявляете, что никогда не ошиблись и никогда не ошибетесь. Тогда определенный алгоритм не остановится, пока вы не заявите, что этот алгоритм не остановится. Если вы используете достаточно сильную систему, вы можете сделать вывод, что вы никогда не скажете, что она не остановится, и, следовательно, она никогда не остановится и не констатирует, что она останавливается.
Тимоти
11

Просто чтобы прояснить ситуацию: гипотеза Церкви-Тьюринга не имеет ничего общего с какой-то догмой гипотетической Церкви Тьюринга. В этом нет ничего религиозного. Наоборот, это всего лишь гипотеза, обобщающая все наши знания. Здесь нет метафизического подтекста. Вопрос о том, могут ли люди добиться большего, что они могут достичь большего, чем машины, является метафизическим вопросом, поскольку мы не имеем абсолютно никакого отношения к нему, ни намека на то, что может отличить человека от машины. Поэтому этот вопрос следует перенести на metaphysics.stackexchange.com.

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

Но тогда, в то время как проблема остановки для машин Тьюринга больше не является критической, нам теперь приходится иметь дело с проблемой остановки человеческой модели. И диагонализация покажет, что проблема остановки человеческой модели не решаема человеком. Тогда что?

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

Конечно, это противоречило бы учению Иоанна , первое предложение которого было следующим: « В начале было Слово, и Слово было у Бога, и Слово было Бог». Отрицая фундаментальное значение синтаксиса, Слово, таким образом, является очень антихристианским утверждением. Я, конечно, не отстаиваю эту позицию, но, поскольку мой первый взгляд на этот вопрос заключается в том, что он является метафизическим, и, поскольку этот вопрос не приостановлен, представляется естественным рассмотреть все последствия, включая метафизические последствия.

Babou
источник
Некристиан не является синонимом атеиста.
Убадуб
@ubadub Вы совершенно правы. Моя ошибка полностью или, точнее, мое невнимание к главному. Я сделал исправление. Знаете ли вы, что другие религии говорят по этому поводу?
Бабу
несколько школ буддизма классифицировали бы «абсолютную» реальность как невыразимую, то есть за пределами лингвистического описания, и все же понятную (для просвещенных). Это производит интересный набор философских вопросов, которые были предметом буддийской дискуссии на протяжении тысячелетий. Смотрите эту статью: bit.ly/2G71tmk за один дубль, хотя и не единственный. У Гарфилда есть диалектистское прочтение буддизма Мадхьямаки, с которым не все ученые согласны (например, см. «Диалетист Горампы« Свобода от концептуального распространения »?» К. Кассора).
Убадуб
8

Рассмотрим это с другой точки зрения.

  • Логика первого порядка неразрешима, то есть не существует процедуры принятия решения, которая определяет, являются ли произвольные формулы логически допустимыми. (Но набор истинных формул первого порядка является полуразрешимым , то есть, если формула истинна, можно найти доказательство с помощью алгоритма.)
  • Доказатели помогают доказать теоремы в логике первого (или даже более высокого) порядка. Помощник по проверке гарантирует, что доказательство выполнено правильно и может даже помочь решить некоторые случаи. Тем не менее, человеческое взаимодействие требует от корректора помощника правильного ответа.

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

Дэйв Кларк
источник
3

Комментарий Карла Маммерта прибил его.

  1. Мое понимание (поправьте меня, если я ошибаюсь) тезиса Черча-Тьюринга заключается в том, что все, что может быть вычислено, может быть вычислено с помощью машины Тьюринга.

  2. А также, если машина Тьюринга может вычислить, остановится ли другая машина Тьюринга на входе или нет (проблема остановки), вы также можете рассчитать, если другая машина Тьюринга не остановится на данном входе (просто поменяйте местами да на нет и нет да!) - важно, потому что тогда вы могли бы подать эту Машину Тьюринга себе - не остановится ли она на входе? Если да (не останавливается), то нет (останавливается ??). Если нет, то да. Если да, то нет. Если нет, то вы ... хммм.

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

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

Кстати, некоторые отличные лекции по этому вопросу можно найти здесь .

Бинго
источник
3

Нет никаких доказательств того, что человеческий мозг на самом деле является чем-то большим, чем машина Тьюринга. Фактически, кажется, что вся вселенная может быть смоделирована на (достаточно большой) машине Тьюринга.

Люди "умны" из-за умных алгоритмов, которые умно написаны в нейронах, поэтому компьютерные ученые не могут украсть или эффективно реализовать их. Как бы умны ни были эти алгоритмы, они, скорее всего, не могут надежно решить проблему остановки.

ithisa
источник
«кажется, что вся вселенная может быть смоделирована» - нет, не может, потому что принцип неопределенности означает, что мы не можем определить начальное состояние с достаточной точностью, чтобы сделать это. Мы можем смоделировать на вселенную, делая произвольные решения о начальном состоянии, но это не обязательно является моделирование с Вселенной.
Периата Breatta
1
Также нет никаких доказательств того, что все мысли основаны на доказательствах. Совершенно очевидно, что Знание превосходит доказательство, и что знание, основанное на доказательствах, является гораздо более слабой умственной способностью, чем непосредственное знание, не поддающееся доказыванию. Должны ли все знания основываться на доказательствах? Как насчет создания новых знаний напрямую?
Wildcard
1
Цитата из книги Мадлен Л'Энгл «Многие воды» делает эту мысль гораздо более лаконичной, даже если рассматривать ее лишь как возможность, а не как фактическое утверждение: «Некоторые вещи нужно верить, чтобы их видели». Если вы входите в область эпистемологии с допущением, что ничего не существует, если не доказано существование, вы накладываете произвольные ограничения на потенциальный объем знаний.
Wildcard
Для части вселенной вам нужен квант, то есть en.wikipedia.org/wiki/…
Fizz
2

Короче говоря: НЕТ

есть машины Тьюринга, для которых мы (пока) не знаем, останавливаются ли эти машины ( например, гипотеза Коллатца ).

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

Тем не менее, вопрос, который вы отвечаете:

Вы спрашиваете, способен ли человек «принять решение», но само решение определяется как алгоритм, поэтому или мы запускаем алгоритм в наших умах и приходим к правильному выводу (или вообще не делаем вывод: открытые проблемы), или мы просто делаем предположение.

Теория вычислений о:

  • Предположим, что существует алгоритм черного ящика (Oracle), который может ответить «да» или «нет» на определенные вопросы
  • Затем вы можете использовать его, чтобы ответить на нерешенные вопросы, создав другой алгоритм, который его использует
  • Делая это, вы заканчиваете с противоречием

Это означает, что до тех пор, пока у вас есть какая-либо система, которая хочет получить Noили Yesответить, Oracle не совместим с этой системой, поэтому Oracles могут фактически существовать, но у нас нет возможности сообщить их результаты , потому что если мы сможем сообщить их результаты, то мы в конечном итоге где-то противоречие.

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

У меня был ответ, но я прочитал это ..

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

Разработчик игр
источник
почему понижает? Тот факт, что сообщение о результате оракула невозможно, является очень глубоким и интересным моментом, который также отвечает на вопрос.
GameDeveloper
Но разве вы не думаете, что люди в конечном итоге докажут или опровергнут такие проблемы, как гипотеза Коллатца
DollarAkshay
1

как и в случае с ответами ДК (и в некоторой степени расширить его), существует сильный смысл, в котором этот вопрос (комбинация человека и компьютера в поиске решений в частном случае для решения проблемы остановки) связан с областью СПС, автоматизированного доказательства теорем и тесно связанные с компьютером доказательства . также давно известно, что существует сильная связь между программами и доказательствами в соответствии Карри-Ховарда . также связано / похоже с этим является завершение программы (например, с помощью инвариантов цикла или вариантов цикла ). на самом деле есть глубокий смысл, в котором всеМатематика об этой проблеме, потому что практически все математические утверждения могут быть преобразованы в вопросы о конкретных программах на ТМ остановки или не остановки. см. например [2] для получения дополнительной информации и множества других ссылок на ATP и т. д.

[1] является знаменитой книгой на эту тему, которая подробно рассматривает вопрос, связывая его с возможностью искусственного интеллекта. Вкратце, идея Пенроуза заключается в том, что истинный ИИ должен быть невозможным, потому что люди могут выдвигать доказательства неразрешимости, такие как проблема остановки Туринга или доказательство неполноты Годельса, тогда как компьютеры не могут из-за того же явления.

[1] Императоры новый разум Пенроуза

[2] приключения и акции в банкоматах , vzn

ВЗН
источник
1
Я не понимаю, как кто-то может понизить этот ответ, он связывает много интересного материала. +1 и +100, если бы я только мог.
GameDeveloper
-1

Современные суперкомпьютерные системы, безусловно, могут моделировать поведение хотя бы одного атома. Если можно моделировать отдельные атомы, то можно моделировать и человеческий разум, создав достаточно большую компьютерную систему для моделирования отдельных атомов. Однако я думаю, что одного этого было бы недостаточно. Вам также понадобится источник энтропии, чтобы получить истинные случайные числа для симуляции человеческого разума. Лучшим источником энтропии, вероятно, будет радиоактивный распад или что-то в этом роде. Что это значит?

Я думаю, что человеческий разум более силен, чем машина Тьюринга, потому что ТМ детерминирован. Вы не можете симулировать истинную случайность на машине Тьюринга. (По крайней мере, такое впечатление я получил от следующего обсуждения

https://cstheory.stackexchange.com/questions/1263/truly-random-number-generator-turing-computable

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

Если принять во внимание также случайность окружающей среды, которая взаимодействует с человеческим разумом (например, пища, которую мы едим, как мы спим, ходим, в основном живем своей жизнью), то я, конечно, думаю, что ТМ с энтропией необходим для симуляция человеческого разума. Не забывайте, что человеческий разум также постоянно подвергается воздействию фоновой радиации, которая также может непредсказуемо взаимодействовать с молекулами нашего мозга. Но я думаю, что даже если мы рассмотрим полностью «изолированную» среду (возможно ли это? Потому что, кажется, следующее указывает на то, что это невозможно): http://hps.org/publicinformation/ate/faqs/faqradbods.html.) - в основном сценарий «мозг в банке», вы, вероятно, все равно получите действительно случайные процессы, которые происходят где-то в человеческом мозге. Я уверен, что биолог мог решить эту часть вопроса? Также не забывайте, что человек в некотором смысле также является частью его или ее окружения:

http://en.wikipedia.org/wiki/Human_Microbiome_Project

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

Итак, чтобы ответить на оригинальный вопрос:

Может ли «человек» (как определено в вопросе) решить проблему остановки? Да, если это проблема остановки для всех детерминированных ТМ, и нет, если это проблема для всех ТМ, связанных с источником энтропии.

Кристофер Шмидт
источник
2
Это кажется очень умозрительным. По сути, вы говорите, что человеческий разум включает в себя случайность, что означает, что это не машина Тьюринга, что означает, что он мог бы решить проблему остановки?
Дэвид Ричерби
Вероятно, правильно, что компьютер может симулировать то, что мы знаем об атомах. Но как вы узнали, что то, что мы знаем, это все, что нужно знать? Тогда случайность хороша: если вы будете ждать достаточно долго, если придете к правильному ответу ... среди многих других. Просто используйте достаточно обезьян достаточно долго или найдите нужную книгу в библиотеке Вавилона. Но получить правильный ответ - это еще не все: откуда вы знаете, что это правильный ответ?
Бабу
Машины детерминированного тьюринга не более мощные, чем машины Тьюринга. Случайности недостаточно, чтобы стать выше машин Тьюринга. Смотрите мой ответ
GameDeveloper
-2

Вся человеческая мысль объединяет отдельные проблемы в личный опыт. Мы могли бы убедиться, что адекватно решили проблему, чтобы остановить ее, но мы никогда не знаем наверняка в алгоритмическом смысле, что компьютер может найти решение. Будьте спокойны и следите за своим умом. 99,9% сообщений, происходящих в наших нейронных схемах, не имеют ничего общего с логическим представлением мира. Вместо этого мы имеем дело с «внутренними» чувствами, сенсорными данными и потоком воспоминаний, ассоциаций и отношений, которые постоянно меняются. Вот почему у нас есть научный метод.

Стив
источник
Я думаю, вы неправильно поняли вопрос. Вопрос состоит в том, могут ли люди решить, останавливается ли данная машина Тьюринга, что на самом деле не имеет ничего общего с «решением проблемы в достаточной степени, чтобы остановить». Вы имеете в виду, что мы можем быть «достаточно убеждены», что машина остановится?
Том ван дер Занден