Почему действительно так важна проблема остановки?

Я не понимаю, почему проблема остановки так часто используется, чтобы исключить возможность определения, останавливается ли программа. Википедия [статья] [1] правильно объясняет, что детерминированная машина с конечной памятью либо остановит, либо повторит предыдущее состояние. Вы можете использовать алгоритм, который определяет, зацикливается ли связанный список, для реализации функции остановки с пространственной сложностью O (1).

Мне кажется, что доказательство проблемы остановки является не чем иным, как так называемым «парадоксом», самореферентным (по крайней мере, циклическим) противоречием так же, как парадокс лжеца. Единственный вывод, который она делает, заключается в том, что функция остановки восприимчива к таким некорректным вопросам.

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

4 года спустя : когда я написал это, я только что посмотрел это видео . Программист получает несколько программ, должен определить, какие из них заканчиваются, и видео продолжает объяснять, почему это невозможно. Я был разочарован, потому что я знал, что, учитывая некоторые произвольные программы, есть некоторая возможность, что главный герой сможет доказать, прекратились ли они. Понятие общности как-то потеряно. Разница заключается в том, что «некоторые программы не могут быть завершены», и «ни одна из программ не может быть подтверждена». Многие алгоритмы формально продемонстрированы для этого. Неспособность сделать это различие по каждой отдельной ссылке, которую я нашел в Интернете, заключалась в том, как я пришел к названию этого вопроса. По этой причине я очень ценю ответ это переопределяет функцию остановки как троичную вместо логической.

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

Вам нужен компилятор, который находит максимально быстрый машинный код для данной программы? На самом деле проблема остановки.

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

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

У вас есть антивирусная программа, и вы хотите увидеть, выполняет ли она когда-либо вредоносную инструкцию. На самом деле просто проблема остановки.

Что касается примера из Википедии, то да, вы можете смоделировать современный компьютер как конечный автомат. Но есть две проблемы с этим.

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

2. Вам понадобится состояний, если у вас n бит ОЗУ. Так что для вашего современного компьютера на 8 ГБ это . Это число настолько велико, что вольфрам альфа даже не знает, как его интерпретировать. Когда я делаю он говорит, что у него десятичных цифр. Это явно слишком много для хранения на обычном компьютере.2 32000000000 2 10 9$2^n$$2^{32000000000}$$2^{10^9}$$300000000$

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

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

ОБНОВЛЕНИЕ: Просто для решения пары вопросов, поднятых в комментариях.

@Tyler Fleming Cloutier: «бессмысленная» проблема возникает в доказательстве того, что проблема остановки неразрешима, но в основе неразрешимости действительно лежит бесконечное пространство поиска. Вы ищете объект с заданным свойством, и если он не существует, нет способа узнать, когда вы закончите.

Сложность проблемы может быть связана с количеством квантификаторов. Пытаясь показать, что существует ( ) объект с произвольным свойством, вы должны искать, пока не найдете его. Если ничего не существует, нет способа (в общем) узнать это. Доказать, что все объекты ( ) имеют свойство, сложно, но вы можете искать объект без свойства, чтобы опровергнуть его. Чем больше чередований между и существует, тем сложнее проблема.$\exists$$\forall$

Подробнее об этом смотрите Арифметическая Иерархия . Все что выше неразрешимо, хотя уровень 1 полуразрешим.$\Sigma^0_0=\Pi^0_0$

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

@ Брент: да, это признает, что это решаемо для современных компьютеров. Но это решаемо для конкретной машины. Если вы добавляете USB-накопитель с дисковым пространством, или возможностью хранить в сети, или что-то еще, то машина изменилась, и результат по-прежнему не сохраняется.

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

Дело в том, что машины Тьюринга не имеют бесконечного количества памяти. Никогда не бывает времени, когда на ленту записывается бесконечное количество символов. Вместо этого машина Тьюринга имеет «неограниченную» память, а это означает, что вы можете получать больше источников памяти, когда вам это нужно. Компьютеры такие. Вы можете добавить ОЗУ или USB-накопители, или жесткие диски, или сетевое хранилище. Да, у вас заканчивается память, когда у вас заканчиваются атомы во вселенной. Но неограниченная память - гораздо более полезная модель.

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

Проблема остановки и различные NP-полные задачи (например, задача коммивояжера) прийти вверх много в форме «Почему вы не можете просто сделать программу , которая делает X?», И вы должны быть в состоянии дать объяснение почему это невозможно или неосуществимо в оставшееся время жизни вселенной.

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

Вы можете использовать алгоритм, который определяет, зацикливается ли связанный список, для реализации функции остановки с пространственной сложностью O (1).

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

Проблема остановки для данного компьютера конечного размера не может быть решена на этом компьютере конечного размера. Это может быть решено только на большом компьютере. (Это верно для любого метода, не только для того, который вы предлагаете. Я не собираюсь приводить формальное доказательство, но вот суть. Если компьютер C может запускать N разных программ, из которых хотя бы один P не завершает работу затем компьютер V, который может проверить, должны ли эти N программы останавливаться, также может запускать различные программы верификатора N. Если C и V - это один и тот же компьютер, то P не является одной из N различных программ, которые запускает V, поэтому На компьютере должно быть запущено не менее N + 1 разных программ, что противоречит предположению, что C запускает N разных программ.)

Кроме того, вы не можете просто использовать алгоритм для обнаружения цикла в связанном списке. Вы должны знать, когда остановиться. Вы можете остановиться, выполнив столько шагов, сколько имеется состояний на компьютере. Если программа использует до бит памяти, то она может иметь различных состояний. Это очень быстро становится невозможным. Например, типичный компьютер выполняет порядка миллиарда команд в секунду; один миллиард секунд - немногим более 30 лет. Таким образом, если вы управляете компьютером в течение 8 лет, вы можете проверить, останавливается ли одна программа с 250 миллионами миллиардов потенциальных состояний. Но это только состояний, то есть вы можете протестировать только программу, которая работает в 7 байтах памяти.2 М 2 $M$$2^M$$2^{56}$

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

Таким образом, за исключением парадоксальных программ, проблема остановки решаема

Парадокс не в проблеме, а в попытке ее решить. Для любой данной программы существует алгоритм, который говорит «да», если программа завершается, и «нет», если программа не завершается. Это тривиально: print "yes"или print "no"сделаем. Проблема состоит в том, чтобы определить, кому звонить. Невозможность решения проблемы остановки означает отсутствие алгоритма для такого определения. Причина доказательство использует диагонализацию аргумент в том , что он должен показать , что нетрешение работ; для этого он начинает с произвольного предполагаемого решения и показывает, что он должен пропустить некоторые программы, создав пропущенную программу. Диагонализация (то, что вы неправильно называете «парадоксом») находится в конструкции, а не в результирующей программе. Результирующие программы не являются самоссылочными.

Существует более общий результат, называемый теоремой Райса, который утверждает, что любое нетривиальное свойствопрограмм неразрешима - любое свойство, которое зависит только от поведения программы, а не от того, каким образом она написана (например, «исходный код состоит из менее чем 42 символов?», ясно разрешимо, тогда как «есть ли Программа, исходный код которой содержит менее 42 символов и которая возвращает один и тот же результат для всех входных данных? »- это не так, и« эта программа вообще ничего не выводит? »). Остановка - это только один пример. Это важно, потому что это часто встречается на практике (обычно, мы хотим знать, будет ли программа возвращать результат в разумные сроки, учитывая ограниченные ресурсы компьютера, на котором она работает, но так как это практически не отвечает, мы готовы согласиться на более простой вопрос о том, будет ли программа в конечном итоге завершена при наличии достаточного времени и памяти).

Мне кажется, что проблема остановки является не чем иным, как так называемым «парадоксом», самореферентным (по крайней мере, циклическим) противоречием так же, как парадокс лжеца. Единственный вывод, который она делает, заключается в том, что функция остановки восприимчива к таким некорректным вопросам.

Нет, это не то , что проблема остановки о. Парадоксы, такие как парадокс лжеца, не являются правдой или ложью, они просто не имеют смысла. С другой стороны, детерминистический алгоритм либо остановится для данного ввода, либо будет работать вечно. Функция halts(program, input)имеет совершенно определенное, детерминированное значение для каждой программы, для каждого входа. Мы просто не можем решить это для любой программы. Или, точнее: мы не можем написать программу, которая может решить ее для каждой пары программа / вход.

Аналогичным (возможно, менее абстрактным) примером является функция «занятый бобер» , интуитивно определяемая как Самая длинная последовательность из 1-й машины Тьюринга с состояниями, начиная с пустой ленты, может записать до ее завершения. Для любого существует только конечное число машин Тьюринга, и каждая из них либо завершается в какой-то момент (затем вы можете сосчитать количество единиц), либо она работает вечно (тогда занятому бобру это не безразлично - оно смотрит только на программы, которые завершаются). Итак, функция занятого бобра имеет детерминированное значение для каждого . (Мы даже знаем это за несколько небольшихn n n n Σ ( n $\Sigma(n):=$$n$$n$$n$$n$, потому что мы можем посмотреть на каждую программу и найти доказательства того, почему они никогда не остановятся.) Но не может быть программы, которая вычисляет .$\Sigma(n)$

Я не понимаю, почему проблема остановки так часто используется, чтобы исключить возможность определения, останавливается ли программа. Статья в Википедии правильно объясняет, что детерминированная машина с конечной памятью либо остановит, либо повторит предыдущее состояние. Вы можете использовать алгоритм, который определяет, зацикливается ли связанный список, для реализации функции остановки с пространственной сложностью O (1).

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

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

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

Существует разница между проблемой остановки и доказательством ее неразрешимости. Проблема остановки - это просто спецификация для программы : в качестве входных данных программа получает исходный код программы и входных данных , и программа должна возвращать значение true, если останавливается на входе и false в противном случае. Это очень четкая спецификация; в этом нет ничего парадоксального: каждая пара исходного кода и ввода имеет один четко определенный правильный ответ.P x H P $H$$P$$x$$H$$P$$x$

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

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

Самостоятельная ссылка не парадоксальна!

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

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

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

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

Также обратите внимание, что теория автоматов действительно часто используется в анализе программ и верификации программного обеспечения. Если вы знаете, что является верхним пределом объема памяти, который будет использовать ваш алгоритм, он не сможет работать более шагов и остановится. Но 1. вам нужно знать верхнюю границу количества памяти, которое будет использовать алгоритм, 2. даже тогда решение о том, останавливается ли этот алгоритм или нет, занимает экспоненциальное количество времени, что обычно не очень полезный алгоритм.2 $s$$2^s$

проблема остановки привела к появлению новой математической концепции «неразрешимости», которой раньше не существовало в математике. это было («на первый взгляд парадоксальное») доказательство того, что у некоторых проблем нет «доказательств». это связано с Годельской концепцией недоказуемости. Теорема Годельса предшествовала постановке задачи Тьюринга на несколько лет. Результат Годеля считался довольно абстрактным в то время и был известен только исследователям и специалистам. Формулировка Туринса показала, что принцип неразрешимости был связан с очень практичными / прагматическими / прикладными вопросами в компьютерной науке, такими как определение того, останавливаются ли произвольные программы, и это рассматривается как гораздо менее теоретическая концепция, это проявляется в современных задачах, таких как " (вопрос, могут ли компьютеры обнаружить теоремы) и доказательство завершения программы.

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

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

Эта самоссылочная программа - программа, которая останавливается в том и только в том случае, если она не останавливается, - создана для того, чтобы было легко доказать, что вы не можете решить Halt. Тот факт, что мы доказываем, что X невозможен с помощью техники Y, не означает, что Y является единственной причиной, по которой мы не можем решить X.

Иными словами, мы не только не можем решить Halt, мы не можем обнаружить, что программа - это та программа, которую мы не можем определить, если она останавливается, за исключением грубой меры типа «если для ее выполнения требуется более 1 минуты, притвориться это не останавливает ".

Если вы начнете с проблемы Остановки и сведете к ней другие проблемы, вы в конечном итоге достигнете точки, в которой вы уменьшили почти каждый вопрос о программах по этому поводу. Мы заканчиваем с теоремой Райс:

Пусть S будет некоторым нетривиальным свойством ^1, которое принимает машина Тьюринга. Это означает, что есть по крайней мере одна машина Тьюринга, которая принимает входные данные со свойством S, а другая - нет.

Тогда это неразрешимо, если данная машина Тьюринга T принимает входные данные со свойством S.

Вы хотите знать, принимает ли машина Тьюринга хотя бы целые числа? Неразрешимые.

Вы хотите знать, принимает ли машина Тьюринга арифметические последовательности? Неразрешимые.

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

¹ К property ofэтому не относится механизм того, как это принято - только то, что принято. «Он принимает за 100 или менее шагов» - это свойство, которое он принимает, а не того, что принято.

Вы правы в том, что проблема остановки, как это обычно вводят и заявляют, является простой ошибкой. Это не доказывает, что не может быть трехзначной функции остановки ('halts', 'loops', 'not know'), которая на практике всегда возвращает 'halts' или 'loops' и возвращает только 'don' например, для специально сконструированных угловых шкафов.

Две причины, по которым проблема остановки является существенной:

1) Это одна из первых доказуемо неразрешимых проблем. Даже если бы гипотетически существовал только один «не знаю», он все равно представлял бы огромный математический интерес.

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

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

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

$f(0)=1 \;\land\; f(0)=2$$h$$h(M)$$M$$H$$h$$h$

Я хотел бы предложить другое объяснение важности проблемы остановки, которая касается людей, а не машин.

Это последняя лекция MIT 1986 «Структура и интерпретация» ; профессор спрашивает: "Есть ли вопросы?" и готовится закончить лекцию, когда один из студентов спрашивает: «Это последний вопрос?»

Задумайтесь об этом на мгновение. Как учитель может ответить на это? Если ученик решает противоречить учителю, он не может дать действительного ответа - это похоже на проблему остановки.

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

PS: Если вы не знаете, о каком курсе я говорю, посмотрите его, это круто.

Я легко могу написать программу, которая дает вход n, либо выводит наименьшее простое число p> n, такое что p + 2 также простое число, либо работает вечно, если такого p не существует. Если вы можете решить проблему, чтобы предсказать, будет ли моя программа останавливаться для каждого входа, вы только что решили гипотезу Твин Прайм.

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