Вычислимая функция

Вычислимая функция (или рекурсивная функция) — частично вычислимая функция, которая является полной. То есть вычислимая функция — функция, которая может быть вычислена с помощью машины Тьюринга. Функция $f: \mathbb{N} \to \mathbb{N}$ , которая не является вычислимой, называется невычислимая.

Предположим, у нас есть двухцветная машина Тьюринга $T$ . Учитывая положительное целое число $n$ , мы устанавливаем ленту пустой, за исключением $n$ последовательных записей, крайняя левая из которых находится в положении головки TM. Мы моделируем машину Тьюринга, и происходит одно из следующих событий:

Она останавливается с $m \in \mathbb{N}$ последовательностей на ленте, с головкой, расположенной на крайнем левом. В этом случае мы говорим, что $T$ результаты — $m$ -заданный ввод $n$ .
Она останавливается, но у неё нет конфигурации, описанной выше.
Она не останавливается.

Пусть $f$ — множество всех упорядоченных пар $(m, n)$ , для которых $T$ выводит $m$ при заданном вводе $n$ . Мы можем видеть, что $f$ является кусочной функцией с доменным пространством и кодоменом $\mathbb{N}$ . Мы говорим, что $T$ "вычисляет" $f$ , а частично вычислимая функция (или частично рекурсивная функция) — кусочная функция, для которой существует машина Тьюринга, которая её вычисляет.

Невычислимая функция может (эфемистически) относиться к "невычислимой быстрорастущей функции". Существуют функции, которые в конечном итоге доминируют над всеми вычислимыми функциями, самым известным примером является функция занятого бобра. Такие функции неизбежно несовместимы и растут исключительно быстро. Важно отметить, что не все невычислимые функции обладают этим свойством — примером может быть функция $h(n)$ , определённая как $1$ , если $n-i$ (в некотором фиксированном порядке) машина Тьюринга останавливается, и $0$ в противном случае.

Обратите внимание, что невычислимость данной функции, как правило, очень сложна. Например, учитывая невычислимую функцию $f(n)$ , такую как $\Sigma(n)$ , у нас обычно нет очевидного способа вычислить $f(n) \mod 2$ , но это не подразумевает её невычислимость. Например, когда $f(n)$ задаётся как $2 \Sigma(n)$ , то легко показать $f(n) \mod 2 = 0$ , и, следовательно, $f(n) \mod 2$ вычислимо.

Интуитивно понятно, что "почти все" функции над натуральными числами не поддаются вычислению — существует бесчисленное множество вычислимых функций и неисчислимое множество функций над натуральными числами.

Свойства вычислимых функций[]

Теорема: Множество вычислимых функций замкнуто по составу.

Доказательство: Учитывая вычислимые $f$ и $g$ , мы хотим показать, что $g \circ f$ вычислимо. Пусть $S$ — машина Тьюринга, которая вычисляет $f$ , а $T$ — машина Тьюринга, которая вычисляет $g$ , такая, что состояния $S$ и $T$ не пересекаются. Пусть $Q_S$ — состояния $S$ , пусть $q_ {S0}$ — начальное состояние, $q_{SH}$ — состояние остановки, и $\delta_S$ — функция перехода, и тому подобное для $T$ . Затем определите машину Тьюринга $S \circ T$ следующим образом:

$Q_{S \circ T} = (Q_S \backslash q_{SH}) \cup Q_T$
$q_{S \circ T,0} = q_{S0}$
$q_{S \circ T,H} = q_{TH}$
$\delta_{S \circ T} = \delta_S' \cup \delta_T$ где $\delta_S'$ заменяет все экземпляры $q_{SH}$ в $\delta_S$ на $q_{T0}$ .
$Q_{S \circ T}$ ⤳ $Q_{q_{SN}\delta^{\beta}}$ для $N$ не $>^* S$ и $\beta$ вычислимо. Таким образом, вся последовательность вычислима.

Поскольку эта машина Тьюринга эффективно вычисляет $f$ , а затем $g$ , связанная с ней вычислимая функция равна $g \circ f$ . Следовательно, $g \circ f$ вычислимо.

Известные невычислимые функции[]

В настоящее время большинство невычислимых быстрорастущих функций являются производными от функций занятого бобра или Райо.