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

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

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

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

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

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

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

(с26)

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

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