Skip to main content
LibreTexts - Ukrayinska

13.8: Резюме

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

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

    Машини Тьюринга визначаються своїми наборами інструкцій, які є кінцевими множинами п'ятикраток (для кожного стану та прочитаного символу вказують новий стан, написаний символ та рух голови). Кінцеві множини п'ятикраток перераховуються, тому існує спосіб пов'язати число з кожним набором інструкцій машини Тьюринга. Індекс машини Тьюринга - це число, пов'язане з його набором інструкцій за фіксованою такою схемою. Таким чином ми можемо «говорити» про машини Тьюринга опосередковано - кажучи про їх індекси.

    Однією з важливих проблем щодо поведінки машин Тьюринга є те, чи вони в кінцевому підсумку зупиняються. \(h(e, n)\)Дозволяти функція, яка,\(= 1\) якщо машина Тьюринга з індексом\(e\) зупиняється при запуску на вході\(n\), і в\(=0\) іншому випадку. Вона називається функцією зупинки. Питання про те, чи є функція зупинки сама по собі обчислювана Тьюринга, називається проблемою зупинки. Відповідь - ні: проблема зупинки нерозв'язна. Це встановлюється за допомогою діагонального аргументу.

    Проблема зупинки є лише одним із прикладів більшого класу задач виду «можуть\(X\) бути виконані за допомогою машин Тьюринга». Ще однією центральною проблемою логіки є проблема вирішення логіки першого порядку: чи є машина Тьюринга, яка може вирішити, чи є дане речення дійсним чи ні. Ця відома проблема також вирішувалася негативно: проблема рішення нерозв'язна. Це встановлюється аргументом скорочення: ми можемо зв'язати з кожною машиною Тьюринга\(M\) і ввести\(w\) речення першого порядку,\(T(M, w) \lif E(M, w)\) яке є дійсним, якщо\(M\) зупиняється при запуску на вході\(w\). Якби проблема рішення була розв'язною, ми могли б таким чином використовувати її для вирішення проблеми зупинки.