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

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\}$ зліченню. Якби всі функції були обчислені деякою машиною Тьюринга, ми могли б перерахувати набір усіх функцій. Таким чином, є деякі функції, які не є обчислювальними Тьюринга. ◻