Формальные модели вычислений

• Функции, вычислимые по Тьюрингу (1936)
• Лямбда-определимые функции (Чёрч, 1936)
• Частично-рекурсивные функции (Гёдель-Клини, 1936)
• Канонические системы (Пост, 1943)
• Нормальные алгорифмы (Марков, 1954, язык Снобол)
• Машина Колмогорова (1954)
• Машина с неограниченными регистрами (Шепердсон-Стерджис, 1963)

Машина Тьюринга — довольно примитивная разновидность машинных кодов с нынешней точки зрения. Но именно универсальная машина Тьюринга, способная воспроизводить работу любой другой, т.е. выполнять роль интерпретатора, оказала решающее влияние на разработку компьютеров архитектуры фон Неймана (с хранимой программой).