Есть ли какое-либо _достаточное_ условие полноты по Тьюрингу определенного языка программирования ?

ckpunTkuDDuc, 302 просмотра

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

Примечание:
>Ну тогда очевидно, что достаточным условием будет возможность для произвольной программы построить соответствующую машину Тьюринга. :)
А как это к примеру можно доказать? Ведь произвольных программ бесконечно много. Может быть существует некоторый достаточный набор операций, реализовав которые язык будет тьюринг-полным?

Примечание:
Немного неправильно изначально задал вопрос, т.к. достаточных условий много, а про набор операций не указал) Вобщем, теперь более-менее понятно, спасибо за ответы

Ответы:

Ant1973

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

Ant1973

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

Ant1973

Не уверен, что такой набор существует. Во всяком случае, википедия на этот счет говорит следующее: "The specific language features used to achieve Turing-completeness can be quite different; FORTRAN systems would use loop constructs or possibly even GOTO statements to achieve repetition; Haskell and Prolog, lacking looping almost entirely, would use recursion. Turing-completeness is an abstract statement of capability, rather than a prescription of specific language features used to implement that capability."

17 лет назад

RPI.su - самая большая русскоязычная база вопросов и ответов. Наш проект был реализован как продолжение популярного сервиса otvety.google.ru, который был закрыт и удален 30 апреля 2015 года. Мы решили воскресить полезный сервис Ответы Гугл, чтобы любой человек смог публично узнать ответ на свой вопрос у интернет сообщества.

Все вопросы, добавленные на сайт ответов Google, мы скопировали и сохранили здесь. Имена старых пользователей также отображены в том виде, в котором они существовали ранее. Только нужно заново пройти регистрацию, чтобы иметь возможность задавать вопросы, или отвечать другим.

Чтобы связаться с нами по любому вопросу О САЙТЕ (реклама, сотрудничество, отзыв о сервисе), пишите на почту [email protected]. Только все общие вопросы размещайте на сайте, на них ответ по почте не предоставляется.