Действительно ли решение является проблемой остановки, легче, чем люди думают?

Действительно ли решение является проблемой остановки, легче, чем люди думают?

Я думаю, что это точно столь трудно, как люди думают.

Типы будут становиться Тьюрингом, завершенным со временем?

Мое дорогое, они уже!

подчиненные типы действительно походят на хорошую разработку?

Очень так.

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

Как ежедневный программист, я сказал бы, что стоит продолжиться как далеко вниз путь к решению проблем останавливающегося стиля, даже если Вы только приближаетесь к тому пределу и никогда не достигаете его. Как Вы указали, поиск вирусов оказывается ценным. Поиск Google не симулирует быть абсолютным ответом для "нахождения меня лучшим X для Y", но это также особенно полезно. Если я выпускаю новый вирус (muwahaha), который создает больший набор решения или просто проливает свет на существующую проблемную область? Независимо от технического различия некоторые практично разработают и обвинят за последующее "обнаружение и удаление" сервисы.

Я с нетерпением жду реальных научных ответов для Ваших других вопросов...

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

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

Кстати, я думаю, что полнота по Тьюрингу шаблонов показывает, что остановка переоценена. Большинство языков гарантирует, что их компиляторы остановятся; не так C++. Это уменьшает C++ как язык?Я так не думаю; это имеет много дефектов, но компиляции, которые не всегда останавливаются, не являются одним из них.

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

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

См. также: http://en.wikipedia.org/wiki/Halting_problem#Importance_and_consequences

Я не знаю, как твердые люди думают, что это, таким образом, я не могу сказать, легче ли это. Однако Вы правы в своем наблюдении, что неразрешимость проблемы (в целом) не означает, что все экземпляры той проблемы неразрешимы. Например, я могу легко сказать Вам что программа как while false do something завершается (принятие очевидной семантики в то время как и ложь).

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

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

Вау, это один запутанный вопрос.

Во-первых: проблема остановки - это не «проблема» в практическом смысле, как в «проблеме, которую необходимо решить». Это, скорее, утверждение о природе математики, аналогичное теореме Гёделя о неполноте.

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

Третье: Работа на языке Тьюринга Complete не исключает «преимуществ статического анализа» - это просто означает, что у статического анализа есть пределы. Это нормально - в любом случае, есть пределы почти всему, что мы делаем.

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