Машина Тьюринга: различия между версиями
Содержимое удалено Содержимое добавлено
JenVan (обсуждение | вклад) м Откат правок 62.231.181.231 (обс.) к версии 195.39.210.219 |
|||
Строка 160:
{{Рамка}}
== Те́зис Чёрча—Тью́ринга ==
'''Те́зис Чёрча—Тью́ринга''' — фундаментальное утверждение для многих областей науки, таких, как [[w:Теория вычислимости|теория вычислимости]], [[w:Информатика|информатика]], теоретическая кибернетика и др. Это утверждение было высказано [[w:Чёрч, Алонзо|Алонзо Чёрчем]] и [[w:Тьюринг, Алан|Аланом Тьюрингом]] в середине [[w:1930-е|1930-х]] годов.
В самой общей форме оно гласит, что любая интуитивно вычислимая функция является [[w:частично вычислимая функция|частично вычислимой]], или, эквивалентно, может быть вычислена с помощью некоторой [[w:Машина Тьюринга|машины Тьюринга]].
Тезис Чёрча—Тьюринга невозможно строго доказать или опровергнуть, поскольку он устанавливает «равенство» между строго формализованным понятием [[w:частично вычислимая функция|частично вычислимой функции]] и неформальным понятием «интуитивно вычислимой функции».
Строка 172 ⟶ 175 :
== Универсальная машина Тьюринга ==
Программу любой детерминированной машины Тьюринга можно записать, используя некоторый конечный алфавит, состоящий из символов состояния, скобок, стрелки и т.п.; обозначим этот машинный алфавит как <math>\Sigma_1</math>. Тогда универсальной машиной Тьюринга ''U'' для класса машин с сать). Теорема была предложена и доказана [[w:Тьюринг, Алан|Тьюрингом]] в [[w:1947|1947]] г.▼
'''Универсальной машиной Тью́ринга''' называют [[w:машина Тьюринга|машину Тьюринга]], которая может заменить собой любую машину Тьюринга. Получив на вход программу и входные данные, она вычисляет ответ, который вычислила бы по входным данным машина Тьюринга, чья программа была дана на вход.
=== Формальное определение ===
▲Программу любой детерминированной машины Тьюринга можно записать, используя некоторый конечный алфавит, состоящий из символов состояния, скобок, стрелки и т.п.; обозначим этот машинный алфавит как <math>\Sigma_1</math>. Тогда универсальной машиной Тьюринга ''U'' для класса машин с
Теорема об универсальной машине Тьюринга утверждает, что такая машина существует и моделирует другие машины с не более чем квадратичным замедлением (т.е. если исходная машина произвела ''t'' шагов, то универсальная произведёт не более ''ct<sup>2</sup>''). Доказательство у этой теоремы конструктивное (такую машину несложно построить, надо только аккуратно её описать). Теорема была предложена и доказана [[w:Тьюринг, Алан|Тьюрингом]] в [[w:1947|1947]] г.
{{Акмар}}
| |||