imported>Dabmasterars: Добавлена картинка-пример Игры «Жизнь» рекурсивно реализованной в Игре «Жизнь».

2025-10-10T20:02:53Z

Добавлена картинка-пример Игры «Жизнь» рекурсивно реализованной в Игре «Жизнь».

Новая страница

__NOTOC__
[[Файл:OTCA metapixel.gif|мини|[[Игра «Жизнь»]] является полной по Тьюрингу и может моделировать любую систему, [[Рекурсия|включая саму себя]] (на фото).]]
'''Полнота́ по Тью́рингу''' — характеристика исполнителя (множества вычисляющих элементов) в [[Теория вычислимости|теории вычислимости]], означающая возможность реализовать на нём любую [[Вычислимая функция|вычислимую функцию]]. Другими словами, для каждой вычислимой функции существует вычисляющий её элемент (например, [[машина Тьюринга]]) или программа для исполнителя, а все функции, вычисляемые множеством вычислителей, являются вычислимыми функциями (возможно, при некотором кодировании входных и выходных данных).

Свойство названо по имени [[Тьюринг, Алан Матисон|Алана Тьюринга]], разработавшего абстрактный вычислитель
— машину Тьюринга, и давшего определение множества функций, вычислимых посредством машин Тьюринга.

== Примеры ==
Большинство широко используемых [[Язык программирования|языков программирования]] — тьюринг-полные. Это касается как [[Императивное программирование|императивных языков]], таких как [[Паскаль (язык программирования)|Паскаль]], так и [[Язык функционального программирования|функциональных]] ([[Haskell]]) и [[Логическое программирование|языков логического программирования]] ([[Пролог (язык программирования)|Пролог]]). Некоторые языки программирования (Haskell, [[C++]]) обладают тьюринг-полнотой времени компиляции, помимо тьюринг-полноты времени исполнения.

Полны по Тьюрингу [[нормальный алгоритм Маркова]], [[2-теговая система]], [[клеточный автомат]] с [[Правило 110|правилом 110]], ингибиторная [[сеть Петри]], [[Лямбда-исчисление#β-редукция|лямбда-исчисление с бета-редукцией]], [[Неограниченная грамматика|неограниченные грамматики]].

Неполны по Тьюрингу [[Конечный автомат|конечные автоматы]], [[Примитивно рекурсивная функция|примитивно рекурсивные функции]], [[Контекстно-свободная грамматика|контекстно-свободные]] и [[Регулярная грамматика|регулярные]] грамматики.

== Универсальная система ==
В каждом тьюринг-полном классе вычислителей существует универсальный представитель класса, имитирующий выполнение произвольного заданного представителя класса. Так, например, универсальная [[машина Тьюринга]] по ленте, содержащей шифр произвольной заданной машины Тьюринга М и её входной цепочки В, имитирует выполнение М над В. В настоящее время построены универсальные машины Тьюринга, содержащие менее 23 инструкций<ref>[http://www.ini.uzh.ch/~tneary/ T. Neary] {{Wayback|url=http://www.ini.uzh.ch/~tneary/ |date=20150924034951 }} and D. Woods. [http://www.ini.uzh.ch/~tneary/NearyWoods_FI2009.pdf Four small universal Turing machines. Fundamenta Informaticae, 91(1):123-144, 2009.] {{Wayback|url=http://www.ini.uzh.ch/~tneary/NearyWoods_FI2009.pdf |date=20150924034953 }}</ref> для комбинаций числа состояний-символов 4×6, 5×5. Универсальная ингибиторная [[сеть Петри]] содержит 56 вершин<ref>[http://daze.ho.ua Zaitsev D.A.] {{Wayback|url=http://daze.ho.ua/ |date=20220401044239 }} [http://dx.doi.org/10.1109/TSMC.2012.2237549 Toward the Minimal Universal Petri Net, IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2013, 1- 12.]</ref>.

== Примечания ==
{{примечания}}

== Литература ==
* {{книга
| автор = Brainerd, W.S., Landweber, L.H.
| год = 1974
| заглавие = Theory of Computation
| издательство = Wiley
}}

== Ссылки ==
* [http://c2.com/cgi/wiki?TuringComplete c2.com] {{Wayback|url=http://c2.com/cgi/wiki?TuringComplete |date=20050408214232 }}

{{computer-sci-stub}}

[[Категория:Теория алгоритмов]]
[[Категория:Алан Тьюринг]]

Полнота по Тьюрингу - История изменений

imported>Dabmasterars: Добавлена картинка-пример Игры «Жизнь» рекурсивно реализованной в Игре «Жизнь».