Определение вычислимости по Тьюрингу. (с25)

Введя понятие алгоритма как МТ, можно сформулировать понятие вычислимости в этих терминах.

С каждой МТ можно связать некоторую функцию. Понятие вычислимости нетривиально. Функцию можно задать, но не знать алгоритма её вычисления. Функция вычислима если существует алгоритм, который её вычисляет и невычислима если алгоритма не существует.

Будем рассматривать функции f следующего типа f: A^* →A^*, где А^* - множество всех слов конечной длины в алфавите A.

Говорят, что МТ вычисляет функцию f_мт, если для любого выполнено:

Функция f называется вычислимой по Тьюрингу, если существует МТ которая её правильно вычисляет.

Скажем, что две МТ Т₁ и Т₂ эквивалентны, если они вычисляют одинаковые функции.

(с26)

Будем считать, что алфавит А МТ содержит 1.

МТ правильно вычисляет функцию , если