Эти виды программ могут существовать на каждом полном по Тьюрингу языке?
На каждом полном по Тьюрингу языке, это возможный создать работу
Компилятор для себя, который сначала работает на интерпретаторе, записанном на некотором другом языке, и затем компилирует свой собственный исходный код? (Начальная загрузка)
Стандарты-Compilant компилятор C++, который выходные двоичные файлы для, например: Windows?
Regex Parser и Evaluater?
Клон World of Warcraft? (Принятие языка получает необходимую привязку API как, например, OpenGL и исходный код WoW доступны),
(Все здесь теоретическое)
Давайте возьмем Brainf*ck в качестве языка в качестве примера.
8 ответов
Все, что действительно требуется для полноты по Тьюрингу, - это умение выполнять простую математику, иметь некоторые переменные и выполнять цикл while. Или любое количество эквивалентных вещей. Если вы хотите создавать настоящие программы, вам нужно немного больше (особенно системные вызовы), и вам также нужно беспокоиться об эффективности (машины Тьюринга могут быть очень медленными ...) Теоретически нет разницы между системами, эквивалентными Тьюрингу, но на практике Там есть.
Если кто-нибудь создаст клиент WoW в BF, я буду очень впечатлен!
Turing-Complete только выражает вычислительные возможности , ничего о возможности ввода / вывода !
Каждый полный по Тьюрингу язык может вычислять один и тот же набор функций. Итак, полный по Тьюрингу язык может делать все, что вы написали, потому что эти вещи вычисляются с другими полными по Тьюрингу языками.
Любой алгоритм, который может быть реализован на одном языке Тьюринга, может быть реализован на любом другом. Ваши вопросы больше относятся к службам операционной системы и API, которые должны быть доступны на соответствующем языке.
Короче говоря, с формальной языковой точки зрения, на все вышеперечисленное ответ положительный.
Можно ли в каждом Тьюринг-полном языке создать работающий...
Если один Тьюринг-полный язык может это сделать, тогда они все могут. В этом смысле они все одинаково "мощные". Поскольку все, что вы описали, уже существует по крайней мере в одном Тьюринг-полном языке, любая из этих программ может быть написана на любом другом Тьюринг-полном языке.
Однако, если что-то возможно, это не значит, что это легко или даже выполнимо. Это очень важное различие, и оно является основой того, почему существуют различные языки программирования. Они не все одинаково хороши для создания определенных видов программного обеспечения - если бы это было так, нам нужен был бы только один язык!
Да, конечно, все эти. В конце концов, именно это и означает «полный по Тьюрингу»: он может вычислить все, что можно вычислить.
Теоретически, да. Но гораздо более интересен вопрос, будет ли это практически возможно при наличии определенного "эзотерического" языка программирования.
Нет, полнота по Тьюрингу не имеет ничего общего с Ввод-вывод и оборудование. Однако вы можете представить, что ввод-вывод, аппаратные системы и графические системы существуют, используя переменные (или «ленту памяти»). В BF вы можете использовать первые 2 ячейки ( x , y ) для «мнимого» разрешения экрана, затем еще x раз y ячеек для всех пикселей на экране, затем следующая ячейка ( n ) для «предполагаемого» размера файловой системы, затем следующие n ячеек для содержимого файловой системы ...