12.8: Варіанти машин Тьюринга

Last updated
Save as PDF

Page ID: 52959

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)

Template:MathJaxZach

Насправді існує багато можливих способів визначення машин Тьюринга, з яких наша лише одна. У чомусь наше визначення більш ліберальне, ніж інші. Ми дозволяємо довільні кінцеві алфавіти, більш обмежене визначення може дозволити тільки два символи стрічки,\(\TMstroke\) і\(\TMblank\). Дозволяємо машині записувати символ на стрічку і одночасно рухатися, інші визначення дозволяють або писати, або рухатися. Допускаємо можливість запису без переміщення головки стрічки, інші визначення залишають поза увагами\(\TMstay\) «інструкцію». Іншими способами наше визначення є більш обмежувальним. Ми припустили, що стрічка нескінченна тільки в одну сторону, інші визначення дозволяють стрічці бути нескінченною як вліво, так і вправо. Насправді можна навіть дозволити будь-яку кількість окремих стрічок, або навіть нескінченну сітку квадратів. Ми представляємо набір інструкцій машини Тьюринга функцією переходу; інші визначення використовують перехідне відношення, коли машина має більше однієї можливої інструкції в будь-якій ситуації.

Це останнє розслаблення визначення особливо цікаве. У нашому визначенні, коли машина знаходиться в стані\(q\) зчитування символу\(\sigma\),\(\delta(q, \sigma)\) визначає, що таке новий символ, стан та положення головки стрічки. Але якщо ми дозволимо набору команд бути співвідношенням між поточними парами символу стану-символу\(\tuple{q, \sigma}\) та новими трійками стану-символ-напрямок\(\tuple{q', \sigma', D}\), дія машини Тьюринга не може бути однозначно визначена - відношення інструкцій може містити обидва\(\tuple{q, \sigma, q', \sigma', D}\) і \(\tuple{q, \sigma, q'', \sigma'', D'}\). В даному випадку у нас є недетермінована машина Тьюринга. Вони відіграють важливу роль у теорії обчислювальної складності.

Існують також різні конвенції щодо того, коли машина Тьюринга зупиняється: ми говоримо, що вона зупиняється, коли функція переходу не визначена, інші визначення вимагають, щоб машина перебувала в спеціальному призначеному стані зупинки. Оскільки стрічки наших машин Тьюринга нескінченні лише в одному напрямку, є випадки, коли машина Тьюринга не може належним чином виконати інструкцію: якщо вона читає крайній лівий квадрат і повинен рухатися вліво. Згідно з нашим визначенням, він просто залишається замість цього, але ми могли б визначити його так, щоб він зупинявся, коли це станеться.

Існують також різні способи представлення чисел (а отже, функція введення-виведення обчислюється машиною Тьюринга): ми використовуємо унарне представлення, але ви також можете використовувати двійкове представлення. Для цього потрібні два символи на додаток до\(\TMblank\) і\(\TMendtape\).

Тепер ось цікавий факт: жодна з цих варіацій не має значення щодо того, які функції Тьюринга обчислюються. Якщо функція Тьюринга обчислюється відповідно до одного визначення, вона Тьюринга обчислюється відповідно до всіх з них.