Существует ли подмножество программ, позволяющих избежать проблемы остановки

Я просто читал еще одно объяснение проблемы остановки, и это заставило меня задуматься о том, что все проблемы, которые я видел, которые приведены в качестве примеров, включают в себя бесконечные последовательности. Но я никогда не использую бесконечные последовательности в своих программах - они занимают слишком много времени. Все приложения реального мира имеют нижнюю и верхнюю границы. Даже действительные числа не являются настоящими действительными значениями - это приблизительные значения, сохраняемые как 32/64 бита и т. Д.

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

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

Чтение из стандартного ввода в качестве примера должно быть ограниченным, но это достаточно просто - я ограничу свой ввод до 10 000 000 символов и т. Д., В зависимости от проблемной области.

ТИА

[Обновить]

После прочтения комментариев и ответов, возможно, мне следует повторить свой вопрос.

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

[Обновление 2]

вот ответ, это да, еще в далеком 1967 году с http://www.isp.uni-luebeck.de/kps07/files/papers/kirner.pdf

О том, что проблема остановки может быть, по крайней мере, теоретически решена для систем с конечным числом состояний, уже утверждал Минский в 1967 году [4]: ​​«... любой конечный автомат, если он полностью предоставлен самому себе, в конечном итоге превратится в совершенно периодический повторяющийся узор. Продолжительность этого повторяющегося шаблона не может превышать количество внутренних состояний машины ... »

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

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

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

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

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

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

Итак, можете ли вы написать язык программирования, который гарантированно создает программы, остановка которых всегда может быть определена? Конечно. Он просто не может иметь циклов, условий и использовать произвольно много памяти. Если вы готовы жить без циклов, без операторов «если» или со строго ограниченным объемом памяти, то, конечно, вы можете написать язык, остановка которого всегда определяется.

Я рекомендую вам прочитать Гедель, Эшер, Бах . Это очень забавная и интересная книга, в которой, помимо прочего, затрагивается теорема Гёделя о неполноте и проблема остановки.

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

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

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

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

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

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

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

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

Какие программы можно проверить с помощью подхода, описанного в статье? По сути, все программы, которые останавливаются перед повторением состояния (где «состояние» примерно соответствует строке кода в программе).

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

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

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

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

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

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

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

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

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

вот ответ, это да, еще в далеком 1967 году с http://www.isp.uni-luebeck.de/kps07/files/papers/kirner.pdf

О том, что проблема остановки может быть, по крайней мере, теоретически решена для систем с конечным числом состояний, уже утверждал Минский в 1967 году [4]: ​​«... любой конечный автомат, если он полностью предоставлен самому себе, в конечном итоге превратится в совершенно периодический повторяющийся узор. Продолжительность этого повторяющегося шаблона не может превышать количество внутренних состояний машины ... »

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

Конечно, как долго это занимает другой вопрос

Есть ли подмножество программ, которые можно определить, если они останавливаются?

Да.

Это достаточно хорошо для большинства программ?

Определите «большинство».

Могу ли я создать набор языковых конструкций, с помощью которых я могу определить «ограничиваемость» программы?

Да.

Есть ли такая вещь, как почти полное завершение, которое достаточно хорошо?

Определите «почти».

Многие люди пишут на Python без использования whileоператора или рекурсии.

Многие люди пишут Java, используя только forоператор с простыми итераторами или счетчиками, которые могут быть тривиально доказаны как завершающие; и они пишут без рекурсии.

Это довольно легко избежать whileи рекурсии.

Для данной программы, в которой все входы ограничены, вы можете определить, останавливается ли программа?

Нет.

Если да, каковы ограничения языка и каковы ограничения входного набора.

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

Стандартный подход к проблеме остановки состоит в том, чтобы позволить доказательствам использовать немного «более богатый» набор математических формализмов, чем те, которые доступны в языке программирования.

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

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

Да. Это называется «Теория группы». Набор значений закрыт под набором операций. Довольно хорошо понятые вещи.