Я видел веб-сайты, которые якобы «доказывают», что HTML5 + CSS является Turing Complete.
Я видел сайты, которые якобы «доказывают», что SQL завершен по Тьюрингу.
Я видел множество веб-сайтов, которые якобы «объясняют», что значит быть завершенным по Тьюрингу.
Достаточно!
Где я могу найти книгу (написанную экспертом в области теории вычислимости) или рецензируемую статью (в авторитетном журнале), в которой показано доказательство: «Этот язык XYZ способен описывать вычислительную машину, обладающую той же вычислительной мощью как машина Тьюринга "?
computability
turing-machines
automata
turing-completeness
church-turing-thesis
Роджер Костелло
источник
источник
Ответы:
Каждый язык, который может реализовать два счетчика (то есть два регистра, которые могут хранить два произвольно больших целых числа) и программу, созданную с помеченной последовательностью этих двух элементарных инструкций, является завершением Тьюринга:C1,C2
Результат доказан в:
Марвин Л. Минский, "Рекурсивная неразрешимость проблемы Поста о метке и других темах в теории машин Тьюринга" (1961)
Не забывайте, что вычислительная модель (в вашем случае язык программирования + устройство, выполняющее программы, написанные на этом языке ) может считаться завершенной по Тьюрингу, только если она поддерживает доступ к неограниченному объему памяти (т. Е. Пространству) или может хранить ( в некоторой форме) сколь угодно большие целые числа. Реализация языка программирования на реальном компьютере эквивалентна линейному ограниченному автомату .
Вы также можете найти много ссылок на страницах Википедии на модели RAM и модели RASP .
Наконец, хорошая книга, посвященная эквивалентности различных моделей вычислений:
«Модели вычислений: введение в теорию вычислимости», Марибель Фернандес
источник
Два наиболее широко используемых учебника по теории вычислимости и сложности:
Существует также прекрасная философская монография для непрофессионалов, которая прорабатывает технические детали теории вычислимости без формальных доказательств.
Наконец, лучшим введением в вычислимость может стать книга-головоломка известного логика:
(Он начинает с множества головоломок, основанных на парадоксе лжеца, а затем прорабатывает создание самореференциального утверждения в виде пазла в стиле Шерлока Холмса о таинственной запертой коробке.)
источник