Skip to main content
LibreTexts - Ukrayinska

12.3: Машини Тьюринга

  1. Last updated
  2. Save as PDF
  • Page ID
    52997

    • \( \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

    Формальне визначення того, що являє собою машину Тьюринга, виглядає абстрактно, але насправді просто: воно просто упаковує в одну математичну структуру всю інформацію, необхідну для уточнення роботи машини Тьюринга. Це включає в себе (1), в якому стані може бути машина, (2) які символи дозволено бути на стрічці, (3) в якому стані машина повинна запуститися, і (4) який набір інструкцій машини.

    Визначення\(\PageIndex{1}\): Turing machine

    Машина Тьюринга\(M\) - це кортеж,\(\langle Q, \Sigma, q_0, \delta\rangle\) що складається з

    1. скінченна сукупність станів\(Q\),
    2. кінцевий алфавіт\(\Sigma\), який включає\(\TMendtape\) і\(\TMblank\),
    3. початковий стан\(q_0 \in Q\),
    4. кінцевий набір інструкцій\(\delta\colon Q \times \Sigma \pto Q \times \Sigma \times \{\TMleft, \TMright, \TMstay\}\).

    Часткова функція також\(\delta\) називається перехідною функцією\(M\).

    Припускаємо, що стрічка нескінченна тільки в одну сторону. З цієї причини корисно позначити спеціальний\(\TMendtape\) символ маркером для лівого кінця стрічки. Це полегшує машинні програми Тьюринга, щоб сказати, коли вони «в небезпеці» запуску з стрічки. Ми могли б припустити, що цей символ ніколи не перезаписується, тобто, що\(\delta(q,\TMendtape) = \tuple{q', \TMendtape, x}\) якщо\(\delta(q,\TMendtape)\) визначено. Деякі підручники так роблять, у нас немає. Ви можете просто бути обережними при побудові вашої машини Тьюринга, яку вона ніколи не перезаписує\(\TMendtape\). Більш того, бувають випадки, коли дозвіл такої перезапису забезпечує деяку зручну гнучкість.

    Приклад\(\PageIndex{1}\)

    навіть машини: парна машина формально чотиримісний\(\tuple{Q, \Sigma, q_0, \delta}\) де\[\begin{aligned} Q & = \{ q_0, q_1 \} \\ \Sigma & = \{ \TMendtape, \TMblank, \TMstroke \}, \\ \delta(q_0, \TMstroke) & = \tuple{q_1, \TMstroke, \TMright},\\ \delta(q_1, \TMstroke) & = \tuple{q_0, \TMstroke, \TMright},\\ \delta(q_1, \TMblank) & = \tuple{q_1, \TMblank, \TMright}.\end{aligned}\]