математика

машина Тьюринга

Машина Тьюринга — это абстрактная вычислительная модель, которая манипулирует символами на ленте.
4 статьи · 1 учёный

Описание

Формально машина Тьюринга состоит из бесконечной ленты, разбитой на ячейки, каждая содержит символ из конечного алфавита; управляющего устройства с конечной памятью состояний; и головки, способной считывать, писать и сдвигаться на одну ячейку. Функция переходов определяет по текущему состоянию и считанному символу новый символ, направление сдвига (Л/П) и новое состояние. Машина начинает работу с входным словом на ленте и может остановиться в принимающем или отвергающем состоянии, либо застрять в бесконечном цикле. Универсальная машина Тьюринга может моделировать любую другую по её описанию — предвосхищение концепции программируемого компьютера.

История

В 1936 году Алан Тьюринг, решая Entscheidungsproblem (проблема разрешения) Давида Гильберта, ввёл понятие «a-машины» (автоматической машины) в статье «On Computable Numbers». Его цель была — формализовать интуитивное понятие алгоритма. Независимо Алонзо Чёрч пришёл к эквивалентному понятию λ-исчисления. Тезис Чёрча-Тьюринга утверждает, что любой интуитивно вычислимый процесс реализуем на машине Тьюринга. В 1945 году Джон фон Нейман использовал эту модель в архитектуре EDVAC — прообразе современных компьютеров. В 1985 году Дэвид Дойч предложил квантовую машину Тьюринга, открыв путь квантовым вычислениям.

Как это работает

Машина Тьюринга вычисляет, манипулируя строками символов. Алгоритмически она эквивалентна языку программирования с одним массивом бесконечной длины. Ключевые свойства: существование универсальной машины (интерпретатор), неразрешимость проблемы остановки (нельзя алгоритмически определить, остановится ли произвольная машина на данном входе), теорема о рекурсии (машина может получить собственное описание). В теории сложности рассматриваются оракульные машины (с дополнительной информацией) и вероятностные машины (с датчиком случайных битов). Квантовые машины Тьюринга оперируют состояниями в гильбертовом пространстве и используют унитарные преобразования; они не нарушают тезис Чёрча-Тьюринга, но могут давать экспоненциальное ускорение для некоторых задач.

Где применяется

Любая компьютерная программа — от калькулятора до ассистента с ИИ — сводится к инструкциям, которые может выполнить машина Тьюринга. На ней основана вся теория вычислений.

Любопытный факт

Простейшая универсальная машина Тьюринга, придуманная Марвином Минским, использует всего 7 состояний и 4 символа — и всё равно способна вычислить всё, что может мощный суперкомпьютер, хотя и чудовищно медленно.

Граф понятий →

Статьи по теме · 16

Четыре дирижёра клеточного оркестра: как эпителий выбирает путь к текучести
Эпителий выстилает наши органы, как плитка — пол. В покое клетки держатся друг за друга, и ткань упруга. Но во время развития зародыша, заживления раны или роста опухоли этот слой начинает течь, как густой мёд. Что именно запускает такое размягчение?
Реставрация Z3: щелчки реле воскрешают утраченный компьютер
Берлин, декабрь 1943. Вспышка бомбы — и первый в истории полностью автоматический программируемый компьютер Z3 исчезает в огне. Его создатель, Конрад Цузе, даже не пытается восстановить железо: после войны он строит новые машины. Но идея Z3 — как утраченная картина, от которой остались лишь эскизы и воспоминания, — ждёт своего часа.
Оркестр без дирижёра: эластичный ганг для LLM-инференса
Семь ядер замерли у невидимого барьера. Восьмое задержалось на чужом процессе — и весь LLM-инференс завис. Так выглядит главная коллизия совместной жизни задач машинного обучения и обычных процессов на одном процессоре. Инференс-ганг требует, чтобы все ядра ударили в такт одновременно — иначе тишина.
Порог 2: как резиновая линейка выдерживает бесконечное усреднение
2 — порог, за которым послушная последовательность рискует потерять свою структуру. Вместо привычной равномерной шкалы — резиновая линейка с неравномерной эластичностью. Именно так устроены пространства Орлича: банаховы пространства последовательностей, где каждому масштабу соответствует своя жёсткость, описываемая выпуклой функцией Юнга (своего рода пружиной).
Химический компьютер в пробирке
В пробирке плавают молекулы. Их количество — скажем, концентрация какого-то белка — становится входным сигналом. А на выходе нужен не просто мутный раствор, а чёткий ответ вроде «да» или «нет». Авторы работы строят химическую цепочку, которая делает именно это.
Почерк без алфавита: как мозг рисует буквы, которых не видел
Рука выводит в воздухе слово «мама» — знакомые дуги и палочки. Мозг при этом не прокручивает фотографию каждой буквы. Он запускает цепочку простых движений. Нейроинженеры проверили эту идею: мысленный почерк — не галерея готовых картинок, а конструктор из одних и тех же двигательных «кирпичиков».
Как заставить молекулярные моторы не буксовать
Внутри каждой клетки кипит жизнь: крошечные белковые машины без устали перетаскивают грузы, считывают гены и исправляют ошибки. Но их работа далека от идеальной — они то и дело «пробуксовывают», делают шаги назад или застревают в бесполезных циклах. Это похоже на городскую пробку, где машины мечутся без толку, сжигая бензин.
Как настроить молекулярный мотор, не ломая голову
Завод, где сотни крошечных сборочных линий работают без остановки. Каждая линия — это молекулярный мотор, который превращает химическое топливо в движение. Чтобы мотор ехал быстрее или в нужную сторону, инженер меняет настройки — форму деталей, силу взаимодействий.
Искусственный разум прокладывает путь к световым чипам
Луч лазера расщепляется на десятки тонких нитей, проходит сквозь мутное стекло и снова собирается в одну точку. Так выглядит рабочий стол, за который села программа. Ей не давали инструкций — только общую цель: разобраться, как свет меняется при прохождении через рассеивающую среду, и найти что-то новое.
Атомная физика2026-04-241 минarXiv:2604.22406экспресс
Ловушки для атомов: как заполнить их под завязку
Оптический пинцет — это луч лазера, который удерживает атом в одной точке, как пальцы держат горошину. Из таких пинцетов собирают целые решётки атомов — основу будущих квантовых компьютеров. Но есть проблема: не в каждый пинцет попадает атом. Обычно заполняется лишь половина ловушек, а для молекул — и того меньше. Пустые места ломают всю конструкцию.
Новые технологии2026-04-181 минarXiv:2604.17109экспресс
Машина, которая не мешает сама себе
Оркестр, где каждый музыкант играет свою партию, но слышит только соседа. Стоит одному сбиться — волна ошибок катится по всему залу. Так работают машины Изинга — специальные устройства для решения задач, где нужно найти лучший вариант из множества. Их элементы-«спины» связаны между собой, и если обновлять их одновременно, они начинают мешать друг другу, как музыканты, вступившие не вовремя.
Квантовая физика2026-04-151 минarXiv:2604.13872экспресс
Танец ионов: рождение квантовых водоворотов
В электромагнитной ловушке исследователи сформировали ионный кристалл — упорядоченную структуру из 150 ионов, охлаждённых до сверхнизких температур. Каждый ион ведёт себя как элементарный магнит, спин которого — вектор, способный ориентироваться в пространстве произвольно.
Идеи, которые никто не искал
Наука похожа на город, где улицы прокладывают сами жители. Там, где уже протоптаны тропы, строят новые дома, а нетронутые пустыри остаются незамеченными — не потому, что там нельзя строить, а потому, что никто туда не заглядывает. В науке такие пустыри — это направления, которые логично вытекают из уже известного, но не приходят в голову учёным, потому что у каждого своя узкая специализация и привычные методы.
Методология2026-02-191 минarXiv:2602.17772экспресс
Мозг печатает сам: как пары электродов ускоряют чтение мыслей
Человек смотрит на экран, где мигают буквы. Он не шевелит ни рукой, ни глазом — только мысленно отмечает нужный символ. Датчики на голове ловят слабые электрические волны мозга, и компьютер понимает, какую букву выбрал человек. Так работает интерфейс «мозг — компьютер»: он даёт голос тем, кто не может говорить или двигаться.
Сверхпроводимость2026-01-101 минarXiv:2601.06632экспресс
Сверхпроводящая память: переключатель, который не забывает
Обычная компьютерная память всё время тратит энергию, чтобы не забыть записанное. Сверхпроводник мог бы хранить данные без потерь, но его трудно заставить переключаться. В новой работе сверхпроводник зажат между двумя магнитными изоляторами. Магнитные слои действуют как два магнита: если их полюса смотрят в одну сторону, сверхпроводимость включена; если в разные — выключена.
Туннельный резонанс: как диоды учатся видеть
В 1974 году физики впервые описали прибор, в котором электроны проходят сквозь энергетический барьер благодаря квантовому туннелированию. Сегодня этот прибор — резонансно-туннельный диод — становится сердцем необычной вычислительной архитектуры.