Я читал в Википедии и некоторых других текстах, которые
Проблема остановки [...] разрешима для линейных ограниченных автоматов (LBA) [и] детерминированных машин с конечной памятью.
Но ранее было написано, что проблема остановки - неразрешимая проблема, и поэтому TM не может ее решить! Так как LBA определены как тип TM, разве это не должно быть для них?
Ответы:
Проблема остановки решаема для любой машины Тьюринга, которая использует известный ограниченный объем пространства, путем обобщения аргумента, данного Йонатаном Н. Если объем пространства равен , размер алфавита равен A , а количество состояний равно Q , то число возможных конфигураций Q S S . Если машина останавливается, то она должна останавливаться на этапах Q S A S , поскольку в противном случае, по принципу «квадратного отверстия», она имеет повторяющуюся конфигурацию и поэтому застревает в бесконечной петле. Поэтому, чтобы определить, останавливается ли машина, мы просто запускаем ее для Q S A SS A Q Q SAS Q SAS Q SAS шаги и посмотреть, остановится ли он в течение этого периода времени.
источник
Вы, кажется, застряли с логической проблемой.
Из того факта, что есть книги, которые вы не можете прочитать, вы не можете сделать вывод, что не можете читать ни одну книгу.
Утверждение о том, что проблема остановки неразрешима для машин Тьюринга (TM), означает лишь то, что существуют машины, для которых нет способа определить, останавливаются они или нет с помощью какой-то единой процедуры, которая всегда останавливается.
Однако есть машины Тьюринга, которые останавливаются. Теперь возьмем подмножество машин Тьюринга, называемых Ниццкими машинами Тьюринга (NTM), которые содержат только машины Тьюринга, которые останавливаются тогда и только тогда, когда лента содержит четное число символов. Если известно, что машина M относится к этому набору, у вас есть простой способ решить, остановится ли M: вы проверяете, является ли количество символов ленты четным (для этого требуется всего два пальца).
Но эта процедура не будет работать для ТМ, которых нет в наборе NTM. (печалька!)
Таким образом, проблема остановки решаема для NTM, но не для TM в целом, даже если набор NTM включен в набор TM.
Это на самом деле критично, а иногда и забывается при интерпретации результата неразрешимости.
Вполне возможно, что можно доказать, что важное свойство неразрешимо для очень большого семейства математических или вычислительных объектов.
Это не означает, что вы должны прекратить искать решение, а только то, что вы не найдете его для всей семьи.
Затем вы можете определить соответствующие подсемейства, для которых решение проблемы остается важным, и попытаться предоставить алгоритмы, чтобы решить, имеет ли свойство свойство для членов этого меньшего семейства.
Как правило, остановка неразрешима для TM в целом, но она разрешима, часто очень просто, для больших и полезных семейств автоматов, которые можно рассматривать как особые случаи TM.
источник
Короче говоря, LBA имеет конечное число конфигураций, скажем D. Следовательно, мы можем выполнить D шагов и подвести итог. Если он работает больше, чем на D шагов, то есть по принципу голубя, можно сказать, что он застрял в бесконечном цикле.
источник