304
правки
Изменения
м
→Другие эквивалентные вычислительные формализмы
* [[Возможность порождения формальной грамматикой произвольного перечислимого языка|произвольные формальные грамматики]]
* [[Лямбда-исчисление|нетипизированное лямбда-исчисление]]
Аланом Тьюрингом было сформулировано следующее утверждение:
{{Утверждение
|about=Тезис Чёрча-Тьюринга
|statement=
Класс перечислимых языков совпадает с классом языков, перечислимых с помощью машин Тьюринга
}}
Иными словами, тезис говорит о том, что любой алгоритм можно запрограммировать на машине Тьюринга.
== Универсальная машина Тьюринга ==
