Машина Тьюринга
Маши́на Тью́ринга — абстрактный исполнитель (абстрактная вычислительная машина) — математическая модель вычислений, предложенная Аланом Тьюрингом в 1936 году для формализации понятия алгоритма.
Машина Тьюринга является расширением конечного автомата и, согласно тезису Чёрча — Тьюринга, способна имитировать всех исполнителей (с помощью задания правил перехода), каким-либо образом реализующих процесс пошагового вычисления, в котором каждый шаг вычисления достаточно элементарен.
То есть всякий интуитивный алгоритм может быть реализован с помощью некоторой машины Тьюринга.
Машина Тьюринга изначально была разработана как теоретический инструмент для изучения границ вычислимости и доказательства невозможности существования алгоритмов для решения некоторых задач. Со временем она стала фундаментальной моделью в теории сложности алгоритмов, служа удобным инструментом для формального исследования алгоритмов. С её помощью можно оценивать временную сложность выполнения алгоритмов и объём памяти, требуемый для вычислений, включая абстрактную оценку, применимую к реальным вычислительным системам.
Устройство
В состав машины Тьюринга входит неограниченная в обе стороны лента (возможны машины Тьюринга, которые имеют несколько бесконечных лент), разделённая на ячейки, и управляющее устройство (также называется головкой записи-чтения), способное находиться в одном из множества состояний. Число возможных состояний управляющего устройства конечно и точно задано.
Управляющее устройство может перемещаться влево и вправо по ленте, оставаться в неподвижном положении, читать и записывать в ячейки символы некоторого конечного алфавита. Выделяется особый пустой символ, заполняющий все клетки ленты, кроме тех из них (конечного числа), на которых записаны входные данные.
Управляющее устройство работает согласно правилам перехода, которые представляют алгоритм, реализуемый данной машиной Тьюринга. Каждое правило перехода предписывает машине, в зависимости от текущего состояния и наблюдаемого в текущей клетке символа, записать в эту клетку новый символ, перейти в новое состояние и переместиться на одну клетку влево или вправо. Некоторые состояния машины Тьюринга могут быть помечены как терминальные, и переход в любое из них означает конец работы, остановку алгоритма.
Машина Тьюринга называется детерминированной, если каждой комбинации состояния и ленточного символа в таблице соответствует не более одного правила. Если существует пара «ленточный символ — состояние», для которой существует 2 и более команд, такая машина Тьюринга называется недетерминированной.
Описание машины Тьюринга
Конкретная машина Тьюринга задаётся перечислением букв алфавита A, множеством состояний Q и набором правил перехода, по которым работает машина. Они имеют вид: qiaj→qi1aj1dk (если головка находится в состоянии qi, а в обозреваемой ячейке записана буква aj, то головка переходит в состояние qi1, в ячейку вместо aj записывается aj1, головка делает движение dk, которое имеет три варианта: на ячейку влево (L), на ячейку вправо (R), остаться на месте (N)). Для каждой возможной конфигурации <qi, aj> имеется ровно одно правило (для недетерминированной машины Тьюринга может быть большее количество правил). Правил нет только для заключительного состояния, попав в которое, машина останавливается. Кроме того, необходимо указать начальное и конечное состояния, начальную конфигурацию на ленте и расположение головки машины.
Пример
Пример машины Тьюринга для умножения чисел в унарной системе счисления. Запись правила перехода «qiaj→qi1aj1R/L/N» следует понимать так: qi — состояние, при котором выполняется это правило, aj — данные в ячейке, в которой находится головка, qi1 — состояние, в которое нужно перейти, aj1 — что нужно записать в ячейку, R/L/N — команда на перемещение.
Машина работает по следующему набору правил:
| q0 | q1 | q2 | q3 | q4 | q5 | q6 | q7 | q8 | |
|---|---|---|---|---|---|---|---|---|---|
| 1 | q01→q01R | q11→q2aR | q21→q21L | q31 → q4aR | q41→q41R | q71→q2aR | |||
| × | q0×→q1×R | q2×→q3×L | q4×→q4×R | q6×→q7×R | q8×→q9×N | ||||
| = | q2=→q2=L | q4=→q4=R | q7=→q8=L | ||||||
| a | q2a→q2aL | q3a→q3aL | q4a→q4aR | q6a→q61R | q7a→q7aR | q8a→q81L | |||
| * | q0*→q0*R | q3*→q6*R | q4*→q51R | ||||||
| q5 →q2*L |
Описание состояний:
| Начало | |
| q0 | начальное состояние. Ищем «x» справа. При нахождении переходим в состояние q1 |
|---|---|
| q1 | заменяем «1» на «а» и переходим в состояние q2 |
| Переносим все «1» из первого числа в результат | |
| q2 | ищем «х» слева. При нахождении переходим в состояние q3 |
| q3 | ищем «1» слева, заменяем её на «а» и переходим в состояние q4. В случае, если «1» закончились, находим «*» и переходим в состояние q6 |
| q4 | переходим в конец (ищем «*» справа), заменяем «*» на «1» и переходим в состояние q5 |
| q5 | добавляем «*» в конец и переходим в состояние q2 |
| Обрабатываем каждый разряд второго числа | |
| q6 | ищем «х» справа и переходим в состояние q7. Пока ищем, заменяем «а» на «1» |
| q7 | ищем «1» или «=» справа, при нахождении «1» заменяем его на «а» и переходим в состояние q2 при нахождении «=» переходим в состояние q8 |
| Конец | |
| q8 | ищем «х» слева. При нахождении переходим в состояние q9. Пока ищем, заменяем «а» на «1» |
| q9 | терминальное состояние (остановка алгоритма) |
Умножим с помощью МТ 3 на 2 в единичной системе. В протоколе указаны начальное и конечное состояния МТ, начальная конфигурация на ленте и расположение головки машины (подчёркнутый символ).
Начало. Находимся в состоянии q0, ввели в машину данные: *111x11=*, головка машины располагается на первом символе *.
1-й шаг. Смотрим по таблице правил, что будет делать машина, находясь в состоянии q0 и над символом «*». Это правило из 1-го столбца 5-й строки — q0*→q0*R. Это значит, что мы переходим в состояние q0 (то есть не меняем его), символ станет «*» (то есть не изменится) и смещаемся по введённому нами тексту «*111x11=*» вправо на одну позицию (R), то есть на 1-й символ 1. В свою очередь, состояние q01 (1-й столбец 1-я строка) обрабатывается правилом q01→q01R. То есть снова происходит просто переход вправо на 1 позицию. Так происходит, пока мы не станем на символ «х». И так далее: берём состояние (индекс при q), берём символ, на котором стоим (подчёркнутый символ), соединяем их и смотрим обработку полученной комбинации по таблице правил.
Простыми словами, алгоритм умножения следующий: помечаем 1-ю единицу 2-го множителя, заменяя её на букву «а», и переносим весь 1-й множитель за знак равенства. Перенос производится путём поочерёдной замены единиц 1-го множителя на «а» и дописывания такого же количества единиц в конце строки (слева от крайнего правого «*»). Затем меняем все «а» до знака умножения «х» обратно на единицы. И цикл повторяется. Действительно, ведь A умножить на В можно представить как А+А+А В раз. Помечаем теперь 2-ю единицу 2-го множителя буквой «а» и снова переносим единицы. Когда до знака «=» не окажется единиц — значит, умножение завершено.
Полнота по Тьюрингу
Можно сказать, что машина Тьюринга представляет собой простейшую вычислительную машину с линейной памятью, которая согласно формальным правилам перехода преобразует входные данные с помощью последовательности элементарных действий.
Элементарность действий заключается в том, что действие меняет лишь небольшой фрагмент данных в памяти (в случае машины Тьюринга лишь одну ячейку), и число возможных действий конечно. Несмотря на простоту машины Тьюринга, на ней можно вычислить всё, что можно вычислить на любой другой машине, осуществляющей вычисления с помощью последовательности элементарных действий. Это свойство называется полнотой.
Один из естественных способов доказательства того, что алгоритмы вычисления, которые можно реализовать на одной машине, можно реализовать и на другой, это имитация первой машины на второй.
Имитация заключается в следующем. На вход второй машине подаётся описание программы (правил работы) первой машины 
и входные данные 
, которые должны были поступить на вход первой машины. Нужно описать такую программу (правила работы второй машины), чтобы в результате вычислений на выходе оказалось то же самое, что вернула бы первая машина, если бы получила на вход данные .
Как было сказано, на машине Тьюринга можно имитировать (с помощью задания правил перехода) все другие исполнители, каким-либо образом реализующие процесс пошагового вычисления, в котором каждый шаг вычисления достаточно элементарен.
На машине Тьюринга можно имитировать машину Поста, нормальные алгоритмы Маркова и любую программу для обычных компьютеров, преобразующую входные данные в выходные по какому-либо алгоритму. В свою очередь, на различных абстрактных исполнителях можно имитировать Машину Тьюринга. Исполнители, для которых это возможно, называются полными по Тьюрингу (Turing complete).
Есть программы для обычных компьютеров, имитирующие работу машины Тьюринга. Но данная имитация неполная, так как в машине Тьюринга присутствует абстрактная бесконечная лента. Бесконечную ленту с данными невозможно в полной мере имитировать на компьютере с конечной памятью: суммарная память компьютера — оперативная память, жёсткие диски, различные внешние носители данных, регистры и кэш процессора и др. — может быть очень большой, но тем не менее всегда конечна. Теоретический предел количества информации, которая может находиться внутри заданной поверхности, с точностью до множителя 
равен энтропии чёрной дыры с той же площадью поверхности.
Варианты машины Тьюринга
Модель машины Тьюринга допускает расширения. Можно рассматривать машины Тьюринга с произвольным числом лент и многомерными лентами с различными ограничениями. Однако все эти машины являются полными по Тьюрингу и моделируются обычной машиной Тьюринга.
Машина Тьюринга, работающая на полубесконечной ленте
В качестве примера такого сведения рассмотрим следующую теорему: Для любой машины Тьюринга существует эквивалентная машина Тьюринга, работающая на полубесконечной ленте (то есть на ленте, бесконечной в одну сторону).
Рассмотрим доказательство, приведённое Ю. Г. Карповым в книге «Теория автоматов». Доказательство этой теоремы конструктивное, то есть мы дадим алгоритм, по которому для любой машины Тьюринга может быть построена эквивалентная машина Тьюринга с объявленным свойством. Во-первых, произвольно занумеруем ячейки рабочей ленты МТ, то есть определим новое расположение информации на ленте:
Затем перенумеруем ячейки, причём будем считать, что символ «*» не содержится в словаре МТ:
Наконец, изменим машину Тьюринга, удвоив число её состояний, и изменим сдвиг головки считывания-записи так, чтобы в одной группе состояний работа машины была бы эквивалентна её работе в заштрихованной зоне, а в другой группе состояний машина работала бы так, как исходная машина работает в незаштрихованной зоне. Если при работе МТ встретится символ ‘*’, значит головка считывания-записи достигла границы зоны:
Начальное состояние новой машины Тьюринга устанавливается в одной или другой зоне в зависимости от того, в какой части исходной ленты располагалась головка считывания-записи в исходной конфигурации. Очевидно, что слева от ограничивающих маркеров «*» лента в эквивалентной машине Тьюринга не используется.
См. также
- Муравей Лэнгтона (двумерная машина Тьюринга)
- Универсальная машина Тьюринга
- Недетерминированная машина Тьюринга
- Вероятностная машина Тьюринга
- Квантовая машина Тьюринга
- Диаграмма Тьюринга
- Машина Минского
- Другие абстрактные исполнители и формальные системы вычислений
- Нормальный алгоритм Маркова ()
- Машина Поста (автоматное программирование)
- Частично рекурсивная функция
Примечания
- Нефёдов, 1992, с. 97.
- Машины Тьюринга. Дата обращения: 14 октября 2023. Архивировано 5 января 2024 года.
- Нефёдов, 1992, с. 94.
- Эббинхауз, 1972, с. 24.
Литература
- Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Глава 8. Введение в теорию машин Тьюринга // Введение в теорию автоматов, языков и вычислений = Introduction to Automata Theory, Languages, and Computation. — М.: , 2002. — 528 с. — ISBN 0-201-44124-1.
- Карпов Ю. Г. Теория автоматов. — Питер, 2003. — ISBN 5-318-00537-3.
- Эббинхауз Г. Д., Якобс К., Ман Ф. К., Хермес Г. Машины Тьюринга и рекурсивные функции. — М.: Мир, 1972. — 262 с.
- Нефёдов В. Н., Осипова В. А. Курс дискретной математики. — М.: МАИ, 1992. — 260 с.
Ссылки
- Машина Тьюринга // Лекция Александра Шеня в проекте ПостНаука (06.04.2013)
У этой статьи есть несколько проблем, помогите их исправить: |
Википедия, чтение, книга, библиотека, поиск, нажмите, истории, книги, статьи, wikipedia, учить, информация, история, скачать, скачать бесплатно, mp3, видео, mp4, 3gp, jpg, jpeg, gif, png, картинка, музыка, песня, фильм, игра, игры, мобильный, телефон, Android, iOS, apple, мобильный телефон, Samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Сеть, компьютер, Информация о Машина Тьюринга, Что такое Машина Тьюринга? Что означает Машина Тьюринга?
Mashi na Tyu ringa abstraktnyj ispolnitel abstraktnaya vychislitelnaya mashina matematicheskaya model vychislenij predlozhennaya Alanom Tyuringom v 1936 godu dlya formalizacii ponyatiya algoritma Hudozhestvennoe predstavlenie mashiny Tyuringa Mashina Tyuringa yavlyaetsya rasshireniem konechnogo avtomata i soglasno tezisu Chyorcha Tyuringa sposobna imitirovat vseh ispolnitelej s pomoshyu zadaniya pravil perehoda kakim libo obrazom realizuyushih process poshagovogo vychisleniya v kotorom kazhdyj shag vychisleniya dostatochno elementaren To est vsyakij intuitivnyj algoritm mozhet byt realizovan s pomoshyu nekotoroj mashiny Tyuringa Mashina Tyuringa iznachalno byla razrabotana kak teoreticheskij instrument dlya izucheniya granic vychislimosti i dokazatelstva nevozmozhnosti sushestvovaniya algoritmov dlya resheniya nekotoryh zadach So vremenem ona stala fundamentalnoj modelyu v teorii slozhnosti algoritmov sluzha udobnym instrumentom dlya formalnogo issledovaniya algoritmov S eyo pomoshyu mozhno ocenivat vremennuyu slozhnost vypolneniya algoritmov i obyom pamyati trebuemyj dlya vychislenij vklyuchaya abstraktnuyu ocenku primenimuyu k realnym vychislitelnym sistemam UstrojstvoV sostav mashiny Tyuringa vhodit neogranichennaya v obe storony lenta vozmozhny mashiny Tyuringa kotorye imeyut neskolko beskonechnyh lent razdelyonnaya na yachejki i upravlyayushee ustrojstvo takzhe nazyvaetsya golovkoj zapisi chteniya sposobnoe nahoditsya v odnom iz mnozhestva sostoyanij Chislo vozmozhnyh sostoyanij upravlyayushego ustrojstva konechno i tochno zadano Upravlyayushee ustrojstvo mozhet peremeshatsya vlevo i vpravo po lente ostavatsya v nepodvizhnom polozhenii chitat i zapisyvat v yachejki simvoly nekotorogo konechnogo alfavita Vydelyaetsya osobyj pustoj simvol zapolnyayushij vse kletki lenty krome teh iz nih konechnogo chisla na kotoryh zapisany vhodnye dannye Upravlyayushee ustrojstvo rabotaet soglasno pravilam perehoda kotorye predstavlyayut algoritm realizuemyj dannoj mashinoj Tyuringa Kazhdoe pravilo perehoda predpisyvaet mashine v zavisimosti ot tekushego sostoyaniya i nablyudaemogo v tekushej kletke simvola zapisat v etu kletku novyj simvol perejti v novoe sostoyanie i peremestitsya na odnu kletku vlevo ili vpravo Nekotorye sostoyaniya mashiny Tyuringa mogut byt pomecheny kak terminalnye i perehod v lyuboe iz nih oznachaet konec raboty ostanovku algoritma Mashina Tyuringa nazyvaetsya determinirovannoj esli kazhdoj kombinacii sostoyaniya i lentochnogo simvola v tablice sootvetstvuet ne bolee odnogo pravila Esli sushestvuet para lentochnyj simvol sostoyanie dlya kotoroj sushestvuet 2 i bolee komand takaya mashina Tyuringa nazyvaetsya nedeterminirovannoj Opisanie mashiny TyuringaKonkretnaya mashina Tyuringa zadayotsya perechisleniem bukv alfavita A mnozhestvom sostoyanij Q i naborom pravil perehoda po kotorym rabotaet mashina Oni imeyut vid qiaj qi1aj1dk esli golovka nahoditsya v sostoyanii qi a v obozrevaemoj yachejke zapisana bukva aj to golovka perehodit v sostoyanie qi1 v yachejku vmesto aj zapisyvaetsya aj1 golovka delaet dvizhenie dk kotoroe imeet tri varianta na yachejku vlevo L na yachejku vpravo R ostatsya na meste N Dlya kazhdoj vozmozhnoj konfiguracii lt qi aj gt imeetsya rovno odno pravilo dlya nedeterminirovannoj mashiny Tyuringa mozhet byt bolshee kolichestvo pravil Pravil net tolko dlya zaklyuchitelnogo sostoyaniya popav v kotoroe mashina ostanavlivaetsya Krome togo neobhodimo ukazat nachalnoe i konechnoe sostoyaniya nachalnuyu konfiguraciyu na lente i raspolozhenie golovki mashiny PrimerSm takzhe Hanojskaya bashnya Reshenie dlya mashiny Tyuringa Primer mashiny Tyuringa dlya umnozheniya chisel v unarnoj sisteme schisleniya Zapis pravila perehoda qiaj qi1aj1R L N sleduet ponimat tak qi sostoyanie pri kotorom vypolnyaetsya eto pravilo aj dannye v yachejke v kotoroj nahoditsya golovka qi1 sostoyanie v kotoroe nuzhno perejti aj1 chto nuzhno zapisat v yachejku R L N komanda na peremeshenie Mashina rabotaet po sleduyushemu naboru pravil q0 q1 q2 q3 q4 q5 q6 q7 q81 q01 q01R q11 q2aR q21 q21L q31 q4aR q41 q41R q71 q2aR q0 q1 R q2 q3 L q4 q4 R q6 q7 R q8 q9 N q2 q2 L q4 q4 R q7 q8 La q2a q2aL q3a q3aL q4a q4aR q6a q61R q7a q7aR q8a q81L q0 q0 R q3 q6 R q4 q51Rq5 q2 L Opisanie sostoyanij Nachaloq0 nachalnoe sostoyanie Ishem x sprava Pri nahozhdenii perehodim v sostoyanie q1q1 zamenyaem 1 na a i perehodim v sostoyanie q2Perenosim vse 1 iz pervogo chisla v rezultatq2 ishem h sleva Pri nahozhdenii perehodim v sostoyanie q3q3 ishem 1 sleva zamenyaem eyo na a i perehodim v sostoyanie q4 V sluchae esli 1 zakonchilis nahodim i perehodim v sostoyanie q6q4 perehodim v konec ishem sprava zamenyaem na 1 i perehodim v sostoyanie q5q5 dobavlyaem v konec i perehodim v sostoyanie q2Obrabatyvaem kazhdyj razryad vtorogo chislaq6 ishem h sprava i perehodim v sostoyanie q7 Poka ishem zamenyaem a na 1 q7 ishem 1 ili sprava pri nahozhdenii 1 zamenyaem ego na a i perehodim v sostoyanie q2 pri nahozhdenii perehodim v sostoyanie q8Konecq8 ishem h sleva Pri nahozhdenii perehodim v sostoyanie q9 Poka ishem zamenyaem a na 1 q9 terminalnoe sostoyanie ostanovka algoritma Umnozhim s pomoshyu MT 3 na 2 v edinichnoj sisteme V protokole ukazany nachalnoe i konechnoe sostoyaniya MT nachalnaya konfiguraciya na lente i raspolozhenie golovki mashiny podchyorknutyj simvol Nachalo Nahodimsya v sostoyanii q0 vveli v mashinu dannye 111x11 golovka mashiny raspolagaetsya na pervom simvole 1 j shag Smotrim po tablice pravil chto budet delat mashina nahodyas v sostoyanii q0 i nad simvolom Eto pravilo iz 1 go stolbca 5 j stroki q0 q0 R Eto znachit chto my perehodim v sostoyanie q0 to est ne menyaem ego simvol stanet to est ne izmenitsya i smeshaemsya po vvedyonnomu nami tekstu 111x11 vpravo na odnu poziciyu R to est na 1 j simvol 1 V svoyu ochered sostoyanie q01 1 j stolbec 1 ya stroka obrabatyvaetsya pravilom q01 q01R To est snova proishodit prosto perehod vpravo na 1 poziciyu Tak proishodit poka my ne stanem na simvol h I tak dalee beryom sostoyanie indeks pri q beryom simvol na kotorom stoim podchyorknutyj simvol soedinyaem ih i smotrim obrabotku poluchennoj kombinacii po tablice pravil Prostymi slovami algoritm umnozheniya sleduyushij pomechaem 1 yu edinicu 2 go mnozhitelya zamenyaya eyo na bukvu a i perenosim ves 1 j mnozhitel za znak ravenstva Perenos proizvoditsya putyom poocheryodnoj zameny edinic 1 go mnozhitelya na a i dopisyvaniya takogo zhe kolichestva edinic v konce stroki sleva ot krajnego pravogo Zatem menyaem vse a do znaka umnozheniya h obratno na edinicy I cikl povtoryaetsya Dejstvitelno ved A umnozhit na V mozhno predstavit kak A A A V raz Pomechaem teper 2 yu edinicu 2 go mnozhitelya bukvoj a i snova perenosim edinicy Kogda do znaka ne okazhetsya edinic znachit umnozhenie zaversheno ProtokolPolnota po TyuringuOsnovnaya statya Polnota po Tyuringu Mozhno skazat chto mashina Tyuringa predstavlyaet soboj prostejshuyu vychislitelnuyu mashinu s linejnoj pamyatyu kotoraya soglasno formalnym pravilam perehoda preobrazuet vhodnye dannye s pomoshyu posledovatelnosti elementarnyh dejstvij Elementarnost dejstvij zaklyuchaetsya v tom chto dejstvie menyaet lish nebolshoj fragment dannyh v pamyati v sluchae mashiny Tyuringa lish odnu yachejku i chislo vozmozhnyh dejstvij konechno Nesmotrya na prostotu mashiny Tyuringa na nej mozhno vychislit vsyo chto mozhno vychislit na lyuboj drugoj mashine osushestvlyayushej vychisleniya s pomoshyu posledovatelnosti elementarnyh dejstvij Eto svojstvo nazyvaetsya polnotoj Odin iz estestvennyh sposobov dokazatelstva togo chto algoritmy vychisleniya kotorye mozhno realizovat na odnoj mashine mozhno realizovat i na drugoj eto imitaciya pervoj mashiny na vtoroj Imitaciya zaklyuchaetsya v sleduyushem Na vhod vtoroj mashine podayotsya opisanie programmy pravil raboty pervoj mashiny D displaystyle D i vhodnye dannye X displaystyle X kotorye dolzhny byli postupit na vhod pervoj mashiny Nuzhno opisat takuyu programmu pravila raboty vtoroj mashiny chtoby v rezultate vychislenij na vyhode okazalos to zhe samoe chto vernula by pervaya mashina esli by poluchila na vhod dannye X displaystyle X Kak bylo skazano na mashine Tyuringa mozhno imitirovat s pomoshyu zadaniya pravil perehoda vse drugie ispolniteli kakim libo obrazom realizuyushie process poshagovogo vychisleniya v kotorom kazhdyj shag vychisleniya dostatochno elementaren Na mashine Tyuringa mozhno imitirovat mashinu Posta normalnye algoritmy Markova i lyubuyu programmu dlya obychnyh kompyuterov preobrazuyushuyu vhodnye dannye v vyhodnye po kakomu libo algoritmu V svoyu ochered na razlichnyh abstraktnyh ispolnitelyah mozhno imitirovat Mashinu Tyuringa Ispolniteli dlya kotoryh eto vozmozhno nazyvayutsya polnymi po Tyuringu Turing complete Est programmy dlya obychnyh kompyuterov imitiruyushie rabotu mashiny Tyuringa No dannaya imitaciya nepolnaya tak kak v mashine Tyuringa prisutstvuet abstraktnaya beskonechnaya lenta Beskonechnuyu lentu s dannymi nevozmozhno v polnoj mere imitirovat na kompyutere s konechnoj pamyatyu summarnaya pamyat kompyutera operativnaya pamyat zhyostkie diski razlichnye vneshnie nositeli dannyh registry i kesh processora i dr mozhet byt ochen bolshoj no tem ne menee vsegda konechna Teoreticheskij predel kolichestva informacii kotoraya mozhet nahoditsya vnutri zadannoj poverhnosti s tochnostyu do mnozhitelya 1 ln 2 displaystyle 1 ln 2 raven entropii chyornoj dyry s toj zhe ploshadyu poverhnosti Varianty mashiny TyuringaModel mashiny Tyuringa dopuskaet rasshireniya Mozhno rassmatrivat mashiny Tyuringa s proizvolnym chislom lent i mnogomernymi lentami s razlichnymi ogranicheniyami Odnako vse eti mashiny yavlyayutsya polnymi po Tyuringu i modeliruyutsya obychnoj mashinoj Tyuringa Mashina Tyuringa rabotayushaya na polubeskonechnoj lente V kachestve primera takogo svedeniya rassmotrim sleduyushuyu teoremu Dlya lyuboj mashiny Tyuringa sushestvuet ekvivalentnaya mashina Tyuringa rabotayushaya na polubeskonechnoj lente to est na lente beskonechnoj v odnu storonu Rassmotrim dokazatelstvo privedyonnoe Yu G Karpovym v knige Teoriya avtomatov Dokazatelstvo etoj teoremy konstruktivnoe to est my dadim algoritm po kotoromu dlya lyuboj mashiny Tyuringa mozhet byt postroena ekvivalentnaya mashina Tyuringa s obyavlennym svojstvom Vo pervyh proizvolno zanumeruem yachejki rabochej lenty MT to est opredelim novoe raspolozhenie informacii na lente Zatem perenumeruem yachejki prichyom budem schitat chto simvol ne soderzhitsya v slovare MT Nakonec izmenim mashinu Tyuringa udvoiv chislo eyo sostoyanij i izmenim sdvig golovki schityvaniya zapisi tak chtoby v odnoj gruppe sostoyanij rabota mashiny byla by ekvivalentna eyo rabote v zashtrihovannoj zone a v drugoj gruppe sostoyanij mashina rabotala by tak kak ishodnaya mashina rabotaet v nezashtrihovannoj zone Esli pri rabote MT vstretitsya simvol znachit golovka schityvaniya zapisi dostigla granicy zony Nachalnoe sostoyanie novoj mashiny Tyuringa ustanavlivaetsya v odnoj ili drugoj zone v zavisimosti ot togo v kakoj chasti ishodnoj lenty raspolagalas golovka schityvaniya zapisi v ishodnoj konfiguracii Ochevidno chto sleva ot ogranichivayushih markerov lenta v ekvivalentnoj mashine Tyuringa ne ispolzuetsya Sm takzheMuravej Lengtona dvumernaya mashina Tyuringa Universalnaya mashina Tyuringa Nedeterminirovannaya mashina Tyuringa Veroyatnostnaya mashina Tyuringa Kvantovaya mashina Tyuringa Diagramma Tyuringa Mashina MinskogoDrugie abstraktnye ispolniteli i formalnye sistemy vychislenijNormalnyj algoritm Markova Mashina Posta avtomatnoe programmirovanie Chastichno rekursivnaya funkciyaPrimechaniyaNefyodov 1992 s 97 Mashiny Tyuringa neopr Data obrasheniya 14 oktyabrya 2023 Arhivirovano 5 yanvarya 2024 goda Nefyodov 1992 s 94 Ebbinhauz 1972 s 24 LiteraturaDzhon Hopkroft Radzhiv Motvani Dzheffri Ulman Glava 8 Vvedenie v teoriyu mashin Tyuringa Vvedenie v teoriyu avtomatov yazykov i vychislenij Introduction to Automata Theory Languages and Computation M 2002 528 s ISBN 0 201 44124 1 Karpov Yu G Teoriya avtomatov Piter 2003 ISBN 5 318 00537 3 Ebbinhauz G D Yakobs K Man F K Hermes G Mashiny Tyuringa i rekursivnye funkcii M Mir 1972 262 s Nefyodov V N Osipova V A Kurs diskretnoj matematiki M MAI 1992 260 s SsylkiV rodstvennyh proektahKnigi v VikiuchebnikeMediafajly na Vikisklade Mashina Tyuringa Lekciya Aleksandra Shenya v proekte PostNauka 06 04 2013 U etoj stati est neskolko problem pomogite ih ispravit V state est spisok istochnikov no ne hvataet snosok Bez snosok slozhno opredelit iz kakogo istochnika vzyato kazhdoe otdelnoe utverzhdenie Vy mozhete uluchshit statyu prostaviv snoski na istochniki podtverzhdayushie informaciyu Svedeniya bez snosok mogut byt udaleny 1 iyulya 2009 Stil etoj stati neenciklopedichen ili narushaet normy literaturnogo russkogo yazyka Statyu sleduet ispravit soglasno stilisticheskim pravilam Vikipedii 3 yanvarya 2019 Pozhalujsta posle ispravleniya problemy isklyuchite eyo iz spiska parametrov Posle ustraneniya vseh nedostatkov etot shablon mozhet byt udalyon lyubym uchastnikom
