Turing Machine

[ˈtjʊərɪŋ məˈʃiːn]
машина Тьюринга
 Теоретическая модель гипотетического вычислительного устройства (абстрактная машина), изобретённого Аланом Тьюрингом (Turing, Alan) для точного определения понятий алгоритма (Algorithm) и вычислимости. Используется в теории алгоритмов; позволяет вывести понятия «алгоритм» (Algorithm) и «вычисление».
 В 1937 г. Тьюринг опубликовал свою работу «О вычислимых числах, с приложением к проблеме разрешимости» (On the Computable Numbers, with an Application to the Entscheidungsproblem), в которой, используя «машины Тьюринга», показал невозможность существования формальной, чисто механической процедуры, которая позволяла бы решать, выводимо ли данное высказывание из некоторого набора математических аксиом. Вместе с К. Гёделем Тьюринг похоронил надежды Д. Гильберта и его последователей, полагавших, что всю математику можно представить в виде набора аксиом и получаемых на их основе теорем. Поскольку машина Тьюринга является абстрактной вычислительной машиной, было доказано, что существует класс логических задач, не разрешимых с помощью любого компьютера.
 Машина Тьюринга послужила основой для создания современного компьютера, объяснив принцип его действия и логические возможности за десятилетие до того, как была сконструирована первая машина такого рода.
Смотри также Abstract Machine

— Игорь Мостицкий (обсуждение) 16:03, 9 января 2026 (MSK)