Тьюринг машинасы

Екі шеті шексіз ұ яшық тарғ а бө лінген лента Тьюринг машинасы болып табылады. Ә рбір ұ яшық та М машинасының сыртқ ы алфавиті деп аталатын символдарының бірі орналасқ ан. Бір символды бос деп белгілеп аламыз. немесе 0 символдарымен белгілейді. Ол ұ яшық тың бос екенін кө рсетеді.

Мысалы, функциясын есептейтін Тьюринг машинасының программасы:

аргументтің бір бос емес ұ яшығ ы ө шірілді

аргументтің бос емес ұ яшық тары оқ ылады

бө луші бос ұ яшық табылды

нә тиженің бос емес ұ яшық тары оқ ылады

нә тиженің бір бос ұ яшығ ы толтырылды

нә тиженің екінші ұ яшығ ы толтырылды

нә тиженің бос емес ұ яшық тары кері ретпен оқ ылады

бос бө лінетін ұ яшық табылды

екінші бос ұ яшық табылды

тағ ы да бос бө лінетін ұ яшық оқ ылады

аргументтің бос емес ұ яшығ ы табылды

аргументтің бос емес ұ яшығ ы табылды

аргументтің бос емес ұ яшық тарының алдында бос ұ яшық табылды

аргументтердің бос емес ұ яшық тары кері ретпен оқ ылады