Главная
Новости
Статьи
Строительство
Ремонт
Дизайн и интерьер
Строительная теплофизика
Прочность сплавов
Основания и фундаменты
Осадочные породы
Прочность дорог
Минералогия глин
Краны башенные
Справочник токаря
Цементный бетон




29.06.2022


27.06.2022


26.06.2022


26.06.2022


25.06.2022


24.06.2022


21.06.2022





Яндекс.Метрика

Универсальная машина Тьюринга

10.03.2022


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

Формальное определение

Программу любой детерминированной машины Тьюринга можно записать, используя некоторый конечный алфавит, состоящий из символов состояния, скобок, стрелки и т. п.; обозначим этот машинный алфавит как Σ 1 {displaystyle Sigma _{1}} . Тогда универсальной машиной Тьюринга U для класса машин с алфавитом Σ 2 {displaystyle Sigma _{2}} и k входными лентами называется машина Тьюринга с k+1 входной лентой и алфавитом Σ 1 ∪ Σ 2 {displaystyle Sigma _{1}cup Sigma _{2}} такая, что если подать на первые k лент входное значение, а на k+1 — правильно записанный код некоторой машины Тьюринга M 1 {displaystyle M_{1}} , то U выдаст тот же ответ, какой выдала бы на этих входных данных M 1 {displaystyle M_{1}} , или будет работать бесконечно долго, если M 1 {displaystyle M_{1}} на этих данных не остановится.

Теорема об универсальной машине Тьюринга утверждает, что такая машина существует и моделирует другие машины с не более чем квадратичным замедлением (то есть если исходная машина произвела t шагов, то универсальная произведёт не более ct²). Доказательство у этой теоремы конструктивное (такую машину несложно построить, надо только аккуратно её описать). Теорема была предложена и доказана Тьюрингом в 1947 г.

Имя:*
E-Mail:
Комментарий: