Что такое полнота по Тьюрингу? Душкин объяснит

• Видео обсуждает полноту по Тьюрингу, которая является свойством вычислительной системы, позволяющим ей вычислять любую вычислимую функцию.  

• Приводится пример лямбда-исчисления, комбинаторной логики, нормального алгоритма Марка, неограниченной формальной грамматики, клеточных автоматов, ингибиторной сети Петри, квантовых вычислений и вычисления на бильярдных шарах.  

• В качестве примеров языков программирования, которые являются полными по Тьюрингу, приводятся императивное программирование (C++, Java), логическое программирование (Prolog) и функциональное программирование (Haskell).