13.2: Перерахування машин Тьюринга

Last updated
Save as PDF

Page ID: 52979

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

Ми можемо показати, що набір всіх машин Тьюринга піддається рахунку. Це випливає з того, що кожну машину Тьюринга можна остаточно описати. Набір станів і словниковий запас стрічки є кінцевими множинами. Функція переходу є частковою функцією\(Q \times \Sigma\) from to\(Q \times \Sigma \times \{\TMleft, \TMright, \TMstay\}\), і тому також може бути вказана шляхом перерахування її значень для скінченно багатьох пар аргументів, для яких вона визначена. Звичайно, строго кажучи, стану і словниковий запас можуть бути якими завгодно; але поведінка машини Тьюринга не залежить від того, якими об'єктами служать стани і словниковий запас. Таким чином, ми можемо припустити, наприклад, що стани і словникові символи є натуральними числами, або що держави і словниковий запас - це всі рядки букв і цифр.

Припустимо, ми виправляємо незліченно нескінченний словниковий запас для визначення машин Тьюринга:\(\sigma_0 = \TMendtape\)\(\sigma_1 = \TMblank\)\(\sigma_2 = \TMstroke\)\(\sigma_3\),\(\TMright\),,\(\TMleft\),\(\TMstay\),,\(q_0\),\(q_1\) ,... Тоді будь-яка машина Тьюринга може бути вказана деяким кінцевим рядком символів з цього алфавіту (хоча не кожен скінченний рядок символів вказує машину Тьюринга). Наприклад, припустимо, у нас є машина Тьюринга,\(M = \tuple{Q, \Sigma, q, \delta}\) де\[\begin{aligned} Q & = \{q'_0, \dots, q'_n\} \subseteq \{q_0, q_1, \dots \} \text{ and}\\ \Sigma & = \{\TMendtape, \sigma'_1, \sigma'_2, \dots, \sigma'_m\} \subseteq \{\sigma_0, \sigma_1, \dots\}.\end{aligned}\] ми могли б вказати його за рядком,\[q'_0 q'_1 \dots q'_n \TMendtape \sigma'_1 \dots \sigma'_m \TMendtape q \TMendtape S(q_0',\sigma'_0)\TMendtape \dots \TMendtape S(q'_n,\sigma'_m)\nonumber\] де\(S(q'_j,\sigma'_i)\) є рядок,\(q'_j \sigma'_i \delta(q'_j, \sigma'_i)\) якщо\(\delta(q'_j, \sigma'_i)\) визначено, і\(q'_j \sigma'_i\) в іншому випадку.

Теорема\(\PageIndex{1}\)

Є функції, від\(\Nat\) до\(\Nat\) яких не піддаються обчислюванню Тьюринга.

Доказ. Ми знаємо, що набір скінченних рядків символів з незліченно нескінченного алфавіту є підрахунковим. Це дає нам, що набір описів машин Тьюринга, як підмножина скінченних рядків з лічильної лексики\(\{q_0, q_1, \dots, \TMendtape, \sigma_1, \sigma_2, \dots\}\), сам по собі перелічується. Оскільки кожна обчислювальна функція Тьюринга обчислюється деякими (насправді, багатьма) машинами Тьюринга, це означає, що набір всіх обчислювальних функцій Тьюринга від\(\Nat\) до\(\Nat\) також перелічується.

З іншого боку, набір всіх функцій від\(\Nat\) до не\(\Nat\) піддається зліченню. Це випливає відразу з того, що навіть безліч всіх функцій одного аргументу від\(\Nat\) до множини піддається\(\{0,1\}\) зліченню. Якби всі функції були обчислені деякою машиною Тьюринга, ми могли б перерахувати набір усіх функцій. Таким чином, є деякі функції, які не є обчислювальними Тьюринга. ◻