Перевод «turing complete» на русский
Lastly, analysts have also mentioned that blockchain Ethereum’s turing complete feature places the hosted ICOs on an increased vulnerability risk.
И последнее, аналитики также упоминали, что полная по Тьюрингу функция блокчейна Ethereum накладывает на размещенные ICO повышенный риск уязвимости.
Dapps development language (decentralized apps) can be any (turing complete) high-level programming language or a specially created language for these purposes.
Языком разработки dApps (децентрализованных приложений) может быть любой (тьюринг полный) высокоуровневый язык программирования или специально разработанный язык для этих целей.
Return-oriented programming builds on the borrowed code chunks approach and extends it to provide Turing complete functionality to the attacker, including loops and conditional branches.
Возвратно-ориентированное программирование расширяет подход заимствования кусков кода, предоставляя атакующему полную по Тьюрингу функциональность, включая циклы и ветвления.
Combinations of cells can act together in predictable manners, and these combined patterns have been shown to be Turing complete.
Комбинации клеток могут действовать сообща в предсказуемом стиле, и эти комбинированные структуры, как видно, являются полными по Тьюрингу.
There exist programming languages that are not Turing complete.
Существуют языки программирования, которые не поддерживают перегрузку.
In 1998 the Z3 was proved to be Turing complete, therefore being the world’s first operational computer.
В 1998 году был Z3 оказалась полной Тьюринга, поэтому первый в мире оперативной компьютера.
XSLT is a Turing complete programming language, and many impressive examples prove its applicability for a number of different tasks.
XSLT — это полный с точки зрения Тьюринга язык программирования, и многие впечатляющие примеры доказывают его применимость для целого ряда самых разнообразных задач.
Quines are possible in any Turing complete programming language, as a direct consequence of Kleene’s recursion theorem.
Куайны возможны в любом тьюринг-полном языке программирования — как следствие теоремы Клини о рекурсии.
As a Turing Complete cryptocurrency platform, Ethereum allows developers to automate business processes by writing smart contracts.
Будучи платформой полной по Тьюрингу (Turing Complete), Ethereum позволяет разработчикам автоматизировать бизнес-процессы с помощью создания смарт-контрактов.
Turing complete programming language of smart contracts «Michelson», which allows implementing any functions and supporting formal verification.
Используется язык программирования смарт-контрактов «Michelson», который позволяет реализовать любые функции и поддерживает формальную проверку.
It just makes you part of that vast majority of the world for whom ideas like «Turing complete» and «end-to-end» are meaningless.
Оно просто относит вас к тому большинству граждан мира, для которых термин «полнота по Тьюрингу» и принцип прозрачности не имеют никакого значения.
Ownership is established through encrypted metadata with the assets programmable through smart contracts operating in a virtual machine which supports contract enforcement and Turing complete programs.
Форма собственности устанавливается через зашифрованные метаданные с активами, программируемые с помощью смарт-контрактов, работающих на виртуальной машине, которая поддерживает выполнение контрактов и Тьюринг-полные программы.
Неожиданная полнота по Тьюрингу повсюду
Полнота по Тьюрингу (Turing-completeness, TC) — это свойство системы при некотором простом представлении ввода и вывода реализовать любую вычислимую функцию.
Тьюринг-полнота — фундаментальное понятие в информатике. Она помогает ответить на многие ключевые вопросы, например, почему невозможно создание идеальной антивирусной программы. Но в то же время она является поразительно распространённым явлением. Казалось бы, компьютерной системе трудно достичь такой универсальности, чтобы выполнять любую программу, но получается наоборот: трудно написать полезную систему, которая немедленно не обратится в полную по Тьюрингу. Оказывается, что даже небольшой контроль над входными данными и преобразованием их в результат, как правило, позволяет создать тьюринг-полную систему. Это может быть забавным, полезным (хотя обычно нет), вредным или чрезвычайно небезопасным и настоящим подарком для хакера (см. о «теоретико-языковой безопасности», которая изучает методы взлома «странных машин» 1 ). Удивительные примеры такого поведения напоминают нам о том, что полнота по Тьюрингу таится повсюду, а защитить систему чрезвычайно сложно.
«Слишком мощные» языки программирования тоже могут спровоцировать неприятные DoS-атаки. Фаззер afl нашёл в OpenBSD такой roff, что способен на генерацию бесконечного цикла, злоупотребляя некоторыми правилами подстановки строк.
Вероятно, эти неожиданные примеры тьюринг-полных систем лучше рассматривать как подмножество «обнаруженных» или «найденных» эзотерических языков программирования. Так что эктраординарно минималистичный по своей сути FRACTRAN не считается 2 , как и специально обфусцированный язык Malbolge (где написание тривиальной программы займёт годы), потому что это специально разработанные эзотерические ЯП. Также не входит в наше подмножество игра «Жизнь», потому что вопросы о тьюринг-полноте появились сразу после её выхода, и признание её полной по Тьюрингу не стало сюрпризом. А учитывая сложность сетей с маршрутизацией и коммутацией пакетов неудивительно, что на этих сетях можно построить клеточный автомат или программировать логические схемы, а планирование/валидация авиабилетов — не только NP-трудная и даже EXPSPACE-трудная задача, но и вовсе неразрешимая (из-за сложных правил авиакомпаний).
Многие конфигурации, специальные языки, инструменты или сложные игры, как выясняется, нарушают правило наименьшей власти и «случайно становятся полными по Тьюрингу», как шаблоны MediaWiki, sed или многократное повторение команд regexp/find-replace в редакторе. Вообще, любая форма замены строк или шаблонирования, или компиляции на лету с высокой вероятностью является тьюринг-полной системой сама или при повторении, так как они часто поддерживают лямбда-исчисление или переписывание термов языка или метки, например, эзотерические языки «///» или Thue.
XSLT, Infinite Minesweeper, Dwarf Fortress 3 , Starcraft, Minecraft, Ant, Transport Tycoon, шаблоны C++ и обобщения Java, ДНК-вычисления и так далее — всё это полные по Тьюрингу системы, и это тоже не удивительно. Многие игры поддерживают скрипты для упрощения разработки и пользовательских модов. Поэтому сделать игру тьюринг-полной элементарно: достаточно включить синтаксис для вызова более известных языков, таких как Perl.
Полнота по Тьюрингу может просто быть малоизвестной частью стандартного формата. Наверное, в наше время многие не знают, что TrueType и многие шрифты — это программы PostScript на стековых машинах, похожие на метаданные ELF и отладочную информацию DWARF. Или что некоторые музыкальные форматы выходят за рамки MIDI, поддерживают скрипты и нуждаются в интерпретации. Если знать о тьюринг-полноте шрифтов, то уже не удивляет полнота по Тюрингу документов TeX, что естественно вызывает многие серьёзные и интересные уязвимости в безопасности шрифтов и медиа, такие как BLEND или Linux-эксплоиты SNES и NES. В других форматах вроде PDF просто ужасное количество уязвимостей 4 . Опять же, выдающиеся достижения вроде создания небольшой машины Тьюринга из кубиков «Лего» или домино 5 , не считаются, поскольку нам уже давно известно, как работают механические компьютеры.
С другой стороны, направление исследований компьютерной безопасности под названием «странные машины» (weird machines) часто выявляет поистине поразительные тьюринг-полные системы. Причём у разных людей они вызывают удивление в разной степени: одним кажется необычным то, что других не удивляет.
- Арифметика Пеано: сложения и умножения натуральных чисел достаточно для полноты по Тьюрингу. Напротив, арифметика Пресбургера лишена умножения и, следовательно, не является полной по Тьюрингу.
- Плитки Вана: разноцветные квадраты, размещение которых задаётся правилом, что соседние стороны двух плиток должны быть одного цвета (исторически понятно для Вана, но система удивила меня, и наверное, многих других людей).
- x86-махинации:
- MMU тасует RAM, чтобы упростить программирование. Если программа правильно особым образом присвоит адреса в памяти, то сможет выполнять произвольные вычисления на MMU с помощью исключений page-faults (комментарии; научная работа), вообще не запуская сам код. Механизм исключений MMU превращается в компьютер с одной инструкцией.
- mov является полной по Тьюрингу системой: безобидная на первый взгляд ассемблерная инструкция mov , которая переносит данные между CPU и RAM, позволяет реализовать компьютер с одной инструкцией на триггер-транспортной архитектуре TTA. На таком компьютере можно играть в Doom (в качестве бонуса: и на инструкциях xor тоже).
- «x86 — тьюринг-полный набор без регистров».
- Аналогичная проблема повреждения памяти возникает в printf из POSIX, в опции %n , как и в других библиотечных функциях C (Карлини и др., 2015). Отсюда и «интерпретатор printbf -Brainfuck в printf .
- Сообщество StarCraft эксплуатировало переполнение буфера в игре для реализации сложных карт, игр жанра «оборонка», игры Mario и редакторов уровней для неё. Эмуляция взлома для защиты модов в обновлённых версиях SC доставила Blizzard много проблем.
- Magic: the Gathering: это тьюринг-полная система, исходя из предположения, что игроки механически соглашаются на предложенный вариант, но в противном случае все действия подчиняются правилам игры
- CSS разработан как декларативный язык разметки для настройки визуального внешнего вида HTML-страниц, но на декларациях CSS можнозакодировать элементарный клеточный автомат Правило 110, который меняет состояние механическими кликами мыши в браузере
- Анимации Microsoft PowerPoint (исключая макросы, VBScript и т. д.) со специальными связями могут реализовать машину Тьюринга (Вильденхайн, 2017: видео; PPT), если пользователь нажимает на активные триггеры анимации
- CSS без щелчков мышью
- SVG: PostScript — это TC по дизайну, но как насчёт более современного формата векторных графических изображений SVG, который написан на XML, то есть на языке документов, который (обычно) не является тьюринг-полным? Похоже, в сочетании с XSLT он всё-таки может быть таковым, но я не нашел никаких доказательств или демонстраций этого в обычном контексте веб-браузера. Стандарт SVG велик и иногда ужасает: неудачная версия стандарта SVG 1.2 пыталась добавить в изображения SVG возможность открытия сетевых сокетов.
- Unicode: Николас Сериот предполагает, что двунаправленные алгоритмы Unicode (предназначенные для отображения письменностей справа налево, таких как арабский или иврит) могут оказаться достаточно сложны для поддержки системы тегов через правила приведения регистра (например, турецкий язык)
См. также
Ссылки
- Обсуждение на HN: 1, 2
- Accidentally Quadratic
- «Кодирующие машины»; «Размышления о делегации доверия», Кен Томпсон, 1984
- «Состязательное перепрограммирование нейронных сетей», Эльсайед и др., 2018
Приложение
Сколько компьютеров в вашем компьютере?
Некоторые увязают в спорах о странных машинах или о том, насколько «большим» станет агент ИИ: будет создан один такой, два, десять или миллионы. Неважно, поскольку это просто организационный вопрос. На самом деле важны входы и выходы системы: насколько работоспособна система в целом и какие ресурсы потребляет? Никого не волнует, если Google работает на 50 суперкомпьютерах, 50 000 мейнфреймах, 5 миллионах серверов, 50 млн встроенных/мобильных процессоров или на сочетании всего перечисленного. Неважно, что Google использует разнообразные чипы: от самодельных «тензорных процессоров» до уникальных кремниевых процессоров (Intel реализует их на чипах на процессоры Xeon для ряда крупнейших клиентов), FPGA, GPU, CPU до ещё более экзотического оборудования вроде квантовых компьютеров D-Wave. Важно только, чтобы она сохраняла конкурентоспособность и могла предоставлять услуги за умеренную плату. В конце концов, сегодня суперкомпьютер выглядит обычно как большое количество серверов в стойках с огромным количеством GPU и необычно высокоскоростными соединениями InfiniBand. То есть суперкомпьютер не так уж сильно отличается от дата-центра, как можно подумать. Любое из перечисленного оборудования может поддерживать многочисленные странные машины в зависимости от своей внутренней динамики и связности.
Аналогично, любую систему ИИ можно реализовать в виде одной гигантской нейронной сети или множества отдельных нейросетей, работающих асинхронно, или как гетерогенный набор микросервисов, или как «общество разума» и так далее. Всё это не особенно важно. С точки зрения сложности или рисков, не так важно, как именно организована система, пока она работает. Систему можно увидеть на многих уровнях, каждый из которых одинаково недействителен сам по себе, но полезен для разных целей в общей системе.
Вот пример плохо определённого вопроса: сколько компьютеров сейчас у вас в карманах и на столе? Сколько компьютеров в вашем «компьютере»? Думаете, только один? Давайте посмотрим внимательнее.
Речь идёт не только о CPU: в наше время транзисторы и процессорные ядра настолько дёшевы, что теперь часто имеет смысл выделять отдельные ядра на задачи реального времени, для повышения производительности, для безопасности, чтобы избежать нагрузки на основную ОС, для совместимости со старой архитектурой или существующего программным пакетом. Просто потому что DSP или ядро быстрее запрограммировать, чем создать специализированный ASIC, или потому что это самое простое из возможных решений. Кроме того, многие из этих компонентов могут использоваться в качестве вычислительных элементов, даже если они не предназначены или вообще скрывают эту функциональность.
-
В обычном процессоре Intel миллиарды транзисторов выполняют множество задач:
- Каждое из 2−8 основных ядер процессора способно работать независимо, включаясь и выключаясь по мере необходимости, у него собственный кэш (больший, чем RAM в большинстве компьютеров до недавнего времени), и его следует рассматривать как независимый компьютер.
- CPU в целом перепрограммируется через микрокод, например, для устранения ошибок дизайна микросхем, и щеголяет всё более непрозрачными объектами, такими как Intel Management Engine (с JVM для программирования; Руан, 2014 и SGX) или Platform Security Processor (PSP) от AMD, или Android TEE. Эти аппаратные модули, как правило, являются полноценными компьютерами в собственном праве, работают независимо от хоста и могут вмешиваться в его работу.
- Любой FPU может стать тьюринг-полной системой через кодирование в операции с плавающей запятой в духе FRACTRAN.
«Удивительно, как много разнородных ядер процессора интегрированы в Intel Silvermont Moorefield SoC (ANN): x86, ARC, LMT, 8051, Audio DSP, каждый на своей прошивке и с поддержкой интерфейса JTAG
Здесь нет ничего необычного в историческом контексте, ведь даже самые первые мейнфреймы обычно включали в себя несколько компьютеров, где основной компьютер выполняет пакетную обработку, о вспомогательные компьютеры обеспечивают высокоскоростные операции ввода/вывода, которые в противном случае помешают основной машине своими прерываниями.
На практике же, кроме сообщества информационой безопасности (поскольку все эти компьютеры небезопасны и, следовательно, полезны для АНБ и вирусописателей), всем остальным пользователям всё равно, что под капотом наших компьютеров скрываются безумно сложные системы, которые более точно рассматривать как пёстрый зверинец из сотен компьютеров, неловко связанных друг с другом (непонятно, «сеть — это компьютер» или «компьютер — это сеть». ). Пользователь воспринимает и использует это как один компьютер.
1. Активная область исследований — создание языков и систем, которые тщательно спроектированы и гарантированно не являются тьюринг-полными (например. тотально функциональное программирование). Зачем прилагать столько усилий для создания языка, на котором невозможно написать многие программы? Дело в том, что полнота по Тьюрингу тесно связана с теоремой Гёделя о неполноте и теоремой Райса. Поэтому если разрешить TC, то мы теряем всевозможные свойства доказуемости. Наоборот, в не полном по Тьюрингу языке легко доказываются разные полезные вещи: например, что программа завершена, типобезопасная она или нет, что её легко преобразовать в логическую теорему, что она потребляет ограниченное количество ресурсов, что реализация протокола верна или эквивалентна другой реализации. Легко доказывается отсутствие побочных эффектов и что программу можно преобразовать в логически эквивалентный, но более быстрый вариант (это особенно важно для декларативных языков вроде SQL, где способность оптимизатора преобразовать запросы — ключ к приемлемой производительности. Хотя, конечно, на SQL можно делать удивительные вещи, такие как градиентный спуск для моделей машинного обучения, а некоторые расширения SQL делают его тьюринг-полным в любом случае, позволяя либо закодировать циклическую систему тегов, либо model DSL, либо вызвать PL/SQL и т.д.
Вот некоторая литература о странных машинах:
- «Программирование эксплоитов: от переполнений буфера до странных машин и теории вычислений», Братус и др., 2011
- «Проблема остановки в безопасности сетевого стека», Сассамэн и др., 2011
- «Странная машина Page-Fault: уроки вычислений без инструкций», Бангерт и др., 2013
- «Странные машины в ELF: фокус на недооценённые метаданные», Shapiro et al 2013
- «Ориентированное на прерывания программирование багдоров: минималистический подход к внедрение багдоров в прошивки встроенных систем», Тан и др., 2014
- «Странные машины в доказательном коде», Ванег, 2014
- «Сигналы цикловой синхронизации — возвращение к портируемому шеллкоду», Босман и Бос, 2014
2. Хотя линейные нейросети эксплуатируют режим плавающей точкой с округлением до нуля для кодирования потенциально тьюринг-полного поведения (для RNN), но это незаметно в нормальной работе, что одновременно является случайным тьюринг-полным поведением и наглядным примером безопасного языка. ↑
3. Dwarf Fortress даёт часовые механизмы, поэтому полнота по Тьюрингу неудивительна. Но и вода реализована как простой клеточный автомат, поэтому есть даже больше способов получить тьюринг-полноту! Сейчас игровая вики называет четыре потенциальных способа создания логических вентилей: жидкости, механизмы часового механизма, минные тележки и логические вентили существ/животных с участием дверей и датчиков давления. ↑
4. Полная спецификация PDF исключительно раздута. Например, в простой программе просмотра PDF с поддержкой достаточного количества спецификации PDF, как браузер Google Chrome, можно играть в Breakout (потому что PDF включает собственное странное подмножество JavaScript). Официальная программа просмотра Adobe PDF поддерживает функциональность вплоть до трёхмерного САПР. ↑
- вычислительная сложность
- полнота по Тьюрингу
- тьюринг-полные системы
- делегация доверия
- ИИ
- странные машины
- FRACTRAN
- теория алгоритмов
- Информационная безопасность
- Компьютерное железо
- Искусственный интеллект
- Настольные компьютеры
- Процессоры
Тьюринг-полнота
Зачастую Тьюринг-эквивалентные языки программирования называют Тьюринг-полными.
В теории вычислимости исполнитель (множество вычисляющих элементов) называется Тьюринг-полным, если на нём можно реализовать любую вычислимую функцию. Другими словами, для каждой вычислимой функции существует вычисляющий её элемент (например, машина Тьюринга) или программа для исполнителя, а все функции, вычисляемые множеством вычислителей, являются вычислимыми функциями (возможно, при некотором кодировании входных и выходных данных).
Любой полный по Тьюрингу язык достаточно универсален, чтобы иметь возможность имитировать любой другой язык (хотя и с потенциальным замедлением в работе). Такие языки эквивалентны в рамках вычислений, которые могут произвести. Полные по Тьюрингу языки настолько распространены, что их можно обнаружить даже в примитивных на первый взгляд системах, например, клеточных автоматах или мозаичных системах.
На практике полнота по Тьюрингу похожа на идеализацию. Компьютеры имеют ограниченное количество памяти, а неограниченная по времени их работа может быть прервана физическим воздействием (выключение, поломка), что как бы ограничивает число задач, которые они могут решить. На самом деле, физические ограничения в контексте Тьюринг-полноты не берутся во внимание: Тьюринг-полный исполнитель не должен быть ограничен по времени и памяти лишь самим исполнителем.
Критерии Тьюринг-полноты
Если на языке программирования можно реализовать машину Тьюринга, то такой язык Тьюринг-полон, и наоборот. Возможность реализации машины Тьюринга на конкретном языке программирования можно грубо описать как перечень требований, которым этот язык должен для этого удовлетворять:
- Конечность (нет бесконечных символьных множеств и пр.).
- Фиксированное описание (формальность [1] ).
- Всегда достаточный объём доступной памяти — в идеале здесь имеется в виду неограниченная память, однако физические рамки не позволяют сделать память ЭВМ бесконечной, поэтому она просто должна быть «always big enough».
- Неограниченность времени выполнения — любая программа в должна иметь возможность работать до тех пор, пока не завершится.
- Возможность функциональной композиции (вызов одной функции из другой, рекурсия).
- Наличие циклов [math][/math] с прерыванием или эквивалентных им конструкций.
- Возможность останавливать выполнение (halt) или каким-то образом подавать сигнал о результатах выполнения.
- Представление множества натуральных чисел, понятие нуля и следующего числа. Возможны другие подобные системы.
- Поддержка входных и выходных данных (I/O), причём без формальных ограничений в объёме. Очевидно, что если любая программа, написанная на каком-то языке программирования, принимает на вход не более фиксированного n бит данных и возвращает не более n бит, этот язык не может быть Тьюринг-полным.
Тьюринг-полнота и неполнота некоторых языков программирования
Доказать Тьюринг-полноту языка программирования можно, предложив способ реализации машины Тьюринга на этом языке. Кроме того, можно предложить на нём интерпретатор Тьюринг-полного языка.
Assembly language
Язык Ассемблера достаточно примитивен относительно языков программирования высокого уровня: он рассчитан на архитектуру с конечной памятью и работает с конечным набором регистров. Однако, не был бы он полным по Тьюрингу, не были бы Тьюринг-полны и любые высокоуровневые языки программирования.
Всё необходимое для машины Тьюринга на asm можно сделать примерно так:
ADDS r0, r0, #1 ; сдвиг ленты вправо ADDS r0, r0, #-1 ; сдвиг ленты влево ADDS [r0], [r0], #1 ; инкремент значения, на которое "указывает" головка ленты ADDS [r0], [r0], #-1 ; декремент значения, на которое "указывает" головка ленты
И далее использовать инструкцию [math]\mathrm[/math] или ей подобную, чтобы выполнять определённую последовательность команд при определённом текущем значении, таким образом обеспечив ветвление.
Pascal
Язык Pascal позволяет смоделировать ленту машины Тьюринга с помощью двунаправленного списка из переменных, создаваемых оператором [math]\mathrm[/math] , семантика которого не предполагает отказа в создании переменной. Также с помощью списков можно смоделировать сколь угодно большие числа. Стандарт не накладывает никаких ограничений: указательный тип абстрактен, множество значений указательного типа языком не ограничено. В Паскале есть еще один тип данных с неограниченным множеством значений, файловый, также пригодный для моделирования ленты машины Тьюринга и представления больших чисел. Достаточно утверждений для очевидности Тьюринг-полноты языка Pascal.
C
В языке C нет высокоуровневого понятия переменной (в смысле Паскаля), есть объекты (object), хранящиеся в памяти как последовательно расположенные байты,имеющие адрес (байты в свою очередь состоят из неадресуемых битов). Целые типы ограничены (конечное множество значений), указатель отождествляется с адресом, постулируется возможность хранить адрес в целочисленной переменной (int или long — зависит от реализации), откуда следует ограниченность множества значений указателей, а стало быть, и ограниченность адресного пространства C-машины. То есть язык C, как и язык ассемблера, ориентирован на архитектуру с конечной памятью. Файл не является типом данных языка C, в отличие от Паскаля. Это вещь из окружения, для работы с которой есть операции над потоками в виде набора библиотечных функций. Тип fpos_t, принятый в стандарте C для позиционирования файлов, постулируется как «отличный от массива тип данных (object type)». Следовательно, множество значений этого типа конечно, а значит, максимальная длина файла в языке C ограничена сверху.
SQL
Сам по себе SQL никогда не считался полным по Тьюрингу языком. Однако, у него существует множество расширений, позволяющих делать рекурсивные запросы, циклы, списки, деревья и пр., например, с помощью PostgreSQL [2] . Более того, на в 2011 г. Habrahabr появилась статья, где показана машина Тьюринга на SQL [3] (в реализации Firebird 2.1, который ограничивает вложенность рекурсивных запросов до 2014 уровней). Тем не менее, всё ещё остаётся ограниченное query execution time.
HTML
HTML можно назвать языком программирования только в контексте формальной полемики. На деле он является языком гипертекстовой разметки и ни чем больше. Т. е. на HTML можно совершить только некоторую ограниченную совокупность действий, интерпретируемых браузером, однако никто не запрещает сделать язык, идентичный по синтаксису с HTML, но интерпретируемый совершенно по другому таким образом, чтобы он был полным по Тьюрингу.
Некоторые другие ЯП
Название языка Год изобретения Парадигма Уровень Зависимость от архитектуры процессора Полнота по Тьюрингу C 1972 Процедурный Низкий зав. от ISO Да C++ 1983 Мультипарадигменный Высокий/Низкий Нет Да Язык Ассемблера 1950 Полнофункциональный Низкий Да Да SQL 1989 Декларативный Высокий Нет Нет Haskell 1990 Функциональный Высокий Нет Да HTML 1986 Декларативный Высокий Нет Нет CSS 1996 Декларативный Высокий Нет Нет Java 1995 Объектно-ориентированный Высокий Нет Да JavaScript 1995 Объектно-ориентированный Высокий Нет Да Python 1991 Объектно-ориентированный Высокий Нет Да XML 1998 Декларативный Высокий Нет Нет Brainfuck 1993 Эзотерический Низкий Да Да Whitespace 2003 Эзотерический Низкий Да Да Интересные случаи полноты по Тьюрингу
Шаблоны C++
Шаблоны C++ позволяют производить сложные вычисления ещё на стадии компиляции программы. Впервые это было продемонстрировано Эрвином Унрухом, который реализовал рекурсивный алгоритм распознавания простых чисел в процессе компиляции. Позже в статье Университета Индиана было продемонстрировано кодирование машины Тьюринга в шаблонах C++ [4] .
Java Generics
Аналогично C++ Templates, Generics, несмотря на свои отличия, тоже оказались полными по Тьюрингу, что было подтверждено Раду Григор в одной из статей Кентского Университета [5] .
URISC
URISC (от англ. Ultimate RISC) — предельный случай процессора типа RISC (буквально: компьютер с предельно сокращённым набором инструкций), который умеет выполнять одну-единственную инструкцию. Обычно это «вычесть и пропустить следующую инструкцию, если вычитаемое было больше уменьшаемого» (англ. «reverse-subtract and skip if borrow»). Аналогичная концепция, основанная именно на «вычесть и перейти, если результат не положительный» (англ. «subtract and branch unless positive»), называется SUBLEQ.
URISC также известен в современной литературе как OISC (англ. One Instruction Set Computer) и является полным по Тьюрингу.
mov
Утилита M/o/Vfuscator превращает любую программу на языке C в огромную последовательность из инструкций [math]\mathrm [/math] [6] .
Тьюринг-полнота
Несколько раз в топиках встречался сабж применительно к языку программирования. AFAIK, полнота какой-либо формальной логики — означает, что есть набор аксиом+правил вывода, а все остальное может быть выведено из этих аксиом посредством механизма вывода. Например, исчисление высказываний полно. Что означает полнота ЯП?
Motl
17.03.05 12:12:08 MSKRe: Тьюринг-полнота
Язык программирования называется Turing-complete тогда, когда он по вычислительным возможностям эквивалентен машине Тьюринга. То есть для любой программы, записанной на ленте этой машины, можно написать программу на данном языке, которая при тех же входных данных будет давать тот же результат.
Машина Тьюринга теоретически может всё, что могут современные компьютеры, и даже больше (т.к. лента у неё бесконечная). Есть т.н. тезис Чёрча (Church), утверждающий, что машина Тьюринга может вычислить всё, для чего человек может определить формальную процедуру вычисления).
Большинство используемых в программировании языков (процедурные, функциональные, объектно-ориентированные) полны по Тьюрингу. Примеры не Turing-complete языков — язык конечных автоматов, язык стековых автоматов (автоматов с магазинной памятью).
ringill ★
( 17.03.05 12:59:01 MSK )Re: Тьюринг-полнота
Мое предположение (я в этих делах полный тьюринг, но думаю моя мысль логична):
Тьюринг-полнота означает что на данном языке можно решить любую в принципе вычислимую задачу.
Также предположу что у большинства попсовых языков ( Це, Паскаль )проблемма с средствами метапрограммирования и потому они Тьюринг-неполные. На них низя написать программу, которая сама пишет другую программу и выполняет ее (путано изложил, но суть я думаю уловима)
ukez
( 17.03.05 13:04:45 MSK )
Ответ на: Re: Тьюринг-полнота от ukez 17.03.05 13:04:45 MSKRe: Тьюринг-полнота
Ты на Цэ, на Васике, на ПостСкрипте, на XSLT, на bash-е и даже на command.com-е можешь написать симулятор машины Тьюринга — следовательно, они — Тьюринг-полные.
vsl☆
( 17.03.05 13:08:35 MSK )
Ответ на: Re: Тьюринг-полнота от vsl 17.03.05 13:08:35 MSKRe: Тьюринг-полнота
ну ваще да. видимо я не прав.
ukez
( 17.03.05 13:16:48 MSK )
Ответ на: Re: Тьюринг-полнота от ukez 17.03.05 13:16:48 MSKRe: Тьюринг-полнота
>Также предположу что у большинства попсовых языков ( Це, >Паскаль )проблемма с средствами метапрограммирования и потому они >Тьюринг-неполные. На них низя написать программу, которая сама пишет >другую программу и выполняет ее (путано изложил, но суть я думаю >уловима)
Очень расплывчато и малоубедительно.
Motl
( 17.03.05 16:33:48 MSK ) автор топика
Ответ на: Re: Тьюринг-полнота от ukez 17.03.05 13:04:45 MSKRe: Тьюринг-полнота
> Также предположу что у большинства попсовых языков ( Це, Паскаль )проблемма с средствами метапрограммирования и потому они Тьюринг-неполные.
доля истины в этом есть — в том что препроцессор Си Тьюринг-неполный.
dilmah ★★★★★
( 17.03.05 16:53:24 MSK )
Ответ на: Re: Тьюринг-полнота от dilmah 17.03.05 16:53:24 MSKRe: Тьюринг-полнота
Однако, Тьюринг-полнота сама по себе не достаточна. Темплейты C++ — Тьюринг-полный язык, но это вовсе не значит, что на них можно сделать всё, что можно сделать на C++.
vsl☆
( 17.03.05 16:58:54 MSK )
Ответ на: Re: Тьюринг-полнота от dilmah 17.03.05 16:53:24 MSK
Re: Тьюринг-полнота
Как видемо я такой эмулятор инаписал. Делать было нечего.