Рубрика «тьюринг-полные системы»

Cities: Skylines — это игра-симулятор города, обладающий достаточной сложностью, чтобы создавать в нём универсальные логические элементы. При помощи универсальных логических элементов можно построить любую схему, в том числе и Тьюринг-полные машины. То есть как и в Minecraft, мы можем создать внутри Cities: Skylines компьютер. Однако было бы очень трудно создавать на основе этих элементов полнофункциональный компьютер, поэтому я продемонстрирую вместо него 4-битный сумматор. Всё выполняется в ванильной версии игры, не требуется ни модов, ни дополнений.

Эта игра, как и любые другие симуляторы строительства города, требует от игрока заниматься подачей в город электричества и воды. Электростанции вырабатывают электричество, для этого им необходима чистая вода и канализационные стоки. Водонапорные башни подают чистую воду, канализационные трубы позволяют избавляться от стоков, и для обоих типов строений требуется электричество. Подобная дуальность между канализацией и водонапорными башнями позволяет создавать элементы AND и OR.

Игра Cities: Skylines оказалась Тьюринг-полной: создаём 4-битный сумматор - 1

Основные участники, слева направо: электростанция на жидком топливе, водонапорная башня, канализационная труба. Сзади стоит ветровая турбина.
Читать полностью »

Каталог программных конструкций, языков и API, которые неожиданно являются полными по Тьюрингу; последствия этого для безопасности и надёжности. Приложение: сколько компьютеров в вашем компьютере?

Любая достаточно сложная программа на Си или Фортране содержит заново написанную, неспецифицированную, глючную и медленную реализацию половины языка Common Lisp. — Десятое правило Гринспена

Полнота по Тьюрингу (Turing-completeness, TC) — это свойство системы при некотором простом представлении ввода и вывода реализовать любую вычислимую функцию.

Тьюринг-полнота — фундаментальное понятие в информатике. Она помогает ответить на многие ключевые вопросы, например, почему невозможно создание идеальной антивирусной программы. Но в то же время она является поразительно распространённым явлением. Казалось бы, компьютерной системе трудно достичь такой универсальности, чтобы выполнять любую программу, но получается наоборот: трудно написать полезную систему, которая немедленно не обратится в полную по Тьюрингу. Оказывается, что даже небольшой контроль над входными данными и преобразованием их в результат, как правило, позволяет создать тьюринг-полную систему. Это может быть забавным, полезным (хотя обычно нет), вредным или чрезвычайно небезопасным и настоящим подарком для хакера (см. о «теоретико-языковой безопасности», которая изучает методы взлома «странных машин»1). Удивительные примеры такого поведения напоминают нам о том, что полнота по Тьюрингу таится повсюду, а защитить систему чрезвычайно сложно.
Читать полностью »


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js