Skip to main content
LibreTexts - Ukrayinska

12.4: Конфігурації та обчислення

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

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

    Нагадаємо, трасування через конфігурації ще машини раніше. Уявний механізм, що складається з стрічки, головки читання/запису та програми машини Тьюринга, насправді просто інтуїтивний спосіб візуалізації того, що таке обчислення машини Тьюринга. Формально ми можемо визначити обчислення машини Тьюринга на заданому вході як послідовність конфігурацій - і конфігурація, в свою чергу, є послідовністю символів (що відповідає вмісту стрічки в даній точці обчислення), число, що вказує на положення головки читання/запису, і держава. Використовуючи їх, ми можемо визначити, що машина Тьюринга\(M\) обчислює на заданому вході.

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

    Конфігурація машини Тьюринга\(M = \tuple{Q, \Sigma, q_0, \delta}\) - це потрійна\(\tuple{C, m, q}\), де

    1. \(C \in \Sigma^*\)є кінцевою послідовністю символів з\(\Sigma\),

    2. \(m \in \Nat\)це число\(< \len{C}\), і

    3. \(q \in Q\)

    Інтуїтивно, послідовність\(C\) - це вміст стрічки (символи всіх квадратів від крайнього лівого квадрата до останнього непорожнього або раніше відвіданого квадрата),\(m\) це номер квадрата, який сканує головка читання/запису (починаючи з\(0\) того, що число крайнього лівого квадрата), і\(q\) є поточним станом машини.

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

    Визначення\(\PageIndex{2}\): Initial configuration

    Початкова конфігурація\(M\) for\(I \in \Sigma^*\) input\[\tuple{\TMendtape \frown I, 1, q_0}.\nonumber\]

    \(\frown\)Символ призначений для конкатенації - ми хочемо переконатися, що між маркером лівого кінця і початком введення немає пропусків.

    Визначення\(\PageIndex{3}\)

    Ми говоримо, що конфігурація\(\tuple{C, m, q}\) дає конфігурацію\(\tuple{C', m', q'}\) в один крок (відповідно до\(M\)), iff

    1. \(m\)-ий символ\(C\) є\(\sigma\),

    2. набір інструкцій\(M\) вказує\(\delta(q, \sigma) = \tuple{q', \sigma', D}\),

    3. \(m\)-ий символ\(C'\) є\(\sigma'\), і

      1. \(D = L\)і\(m' = m - 1\) якщо\(m>0\), інакше\(m'=0\), або

      2. \(D = R\)і\(m' = m + 1\), або

      3. \(D = N\)і\(m' = m\),

    5. якщо\(m' = \len{C}\), то\(\len{C'} = \len{C} + 1\) і\(m'\) -ий символ\(C'\) є\(\TMblank\). Інакше\(\len{C'}=\len{C}\).

    6. для всіх\(i\) таких, що\(i < \len{C}\) і\(i \neq m\)\(C'(i) = C(i)\),

    Визначення\(\PageIndex{4}\)

    Прогін\(M\) на вході\(I\) - це\(C_i\) послідовність конфігурацій\(M\), де\(C_0\) початкова конфігурація\(M\) для введення\(I\), і кожен \(C_i\)врожайність\(C_{i+1}\) в одну сходинку.

    Ми говоримо, що\(M\) зупиняється на вході\(I\) після \(k\)кроків\(C_k = \tuple{C, m, q}\), якщо,\(m\) го символ\(C\) є\(\sigma\), і\(\delta(q, \sigma)\) не визначено. У цьому випадку виходом\(M\) for input\(I\) є\(O\), де\(O\) є рядок символів, які не починаються або закінчуються\(\TMblank\) таким, що\(C = \TMendtape \concat \TMblank^i \concat O \concat \TMblank^j\) для деяких\(i, j \in \Nat\).

    Згідно\(O\) з цим визначенням, висновок\(M\) завжди починається і закінчується символом, відмінним\(k\) від\(\TMblank\), або, якщо в цей час вся стрічка заповнена\(\TMblank\) (крім крайньої лівої\(\TMendtape\)), \(O\)порожній рядок.