Математический форум Math Help Planet
http://mathhelpplanet.com/

Решение "проблемы остановки"
http://mathhelpplanet.com/viewtopic.php?f=51&t=34794
Страница 6 из 6

Автор:  ivashenko [ 31 май 2017, 01:08 ]
Заголовок сообщения:  Re: Решение "проблемы остановки"

O Micron писал(а):
Сегодня мною выяснен недостаток, содержащийся в способе, предложенном мною в первом посте этой темы.

Рассмотрим такой цикл:
Код:
  a=0
label1:
  a=a+1
  if a>0 then label1
  End

Налицо бесконечный цикл, но предложенным способом это обнаружено не будет, потому что ни при одном возврате состояние не будет тем же самым: "a" всё время меняется.


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


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

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


Тема завершена, всем спасибо за обсуждение!
O'Micron.


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

Страница 6 из 6 Часовой пояс: UTC + 3 часа [ Летнее время ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/