Правильная вычислимость функций на машине Тьюринга.

Определение 1. Будем говорить, что машина Тьюринга пра­вильно вычисляет функцию f(x₁, x₂, ..., х_п),, если начальное слово она переводит в слово и при этом в процессе работы не пристраивает к начальному слову но­вых ячеек на ленте ни слева, ни справа. Если же функция f не определена на данном наборе значений аргументов, то, начав работать из указанного положения, она никогда в процессе рабо­ты не будет надстраивать ленту слева.

Пример 1. Приведем программы машин Тьюринга, пра­вильно вычисляющих функции S(x) = х+ 1 и 0(х) = 0. Функция S(x) =х+ 1 осуществляет перевод: q₁01^x0 => q₀01^x+1. Ее программа:

q₁0→ q₂ П; q₂1→ q₂1 П; q₂0→ q₃1; q₃1→ q₃1 Л; q₃0→ q₀0. Функция O(x) = 0 осуществляет перевод: q₁01^x0 => q₀00^x+1. Ее программа: q₁0→ q₂ 0П; q₂1→ q₂1 П; q₂0→ q₃0Л; q₃1→ q₄0; q₄0→ q₃0Л, q₃0→ q₀0.Соответствующую машину Тьюринга обозна­чили О.