Тьюринг машинасының формальді емес анықтамасы

Тьюринг машинасы автомат сияқты, екі жақты шексіз лентасы, басы (головкасы) және басқару құрылғысы бар. Басқару құрылғысы бір қалыпты болуы мүмкін, соңғы көпмүше жасайды Q = {q0, q1, ..., qn}. Көпмүше Q Тьюринг машинасының ішкі алфавиті деп аталады.

Тьюринг машинасының есептегіш машинадан принципті айырмашылығы мынада, оның еске сақтау құрылғысы шексіз лентадан тұрады, сондықтан ол шындыққа жанаспайтын қиялдағы машина болып қала береді. Лента ұяшықтарға бөлінген, әрқайсысына алфавиттің бір символы жазылған соңғы алфавит A={a0,a1,...,am}болады, ол Тьюринг машинасының енгізу алфавиті аталады. Тьюринг машинасы функциясын қолдану кезінде ұяшықтардың соңғы саны толтырылмаған болуы мүмкін. Есептегіш (считывающая) басы әр уақытта лентаның ұяшығына шолу, осы ұяшықтағы символға тәуелді және басқару құрылғысының қалпы ұяшыққа жаңа символ жазады немесе оны өзгертусіз қалдырады, ұяшық оңға немесе солға жылжиды немесе орнында қалады. Осыдан барып басқару құрылғысы жаңа күйге ауысады немесе бұрынғысында қалады. Бастапқы құрылғысының қалпы ортасында бастапқы қалып q₀ және соңғы қалып q_z болып бөлінеді.

Тьюринг машинасының бір тактісі бойынша символды санауға болады, оның орнына жаңасын жазып немесе оны өзгеріссіз қалдырамыз және басын бір ұяшық солға немесе оңға жылжытамыз немесе орнында қалдырамыз.

А алфавиті – кейбір соңғы көпмүше символдары.

Алфавит тізбегі деп осы алфавиттің символдарының тізбегін айтамыз. x тізбектің ұзындығы, ол сол тізбектегі символдар санын көрсетеді және | x | болып белгіленеді. Бос тізбек ұзындығы 0-ге тең.

Тізбек конкатенациясы деп х және у тізбегін айтады, қосылып жазылған символдардан алынған х тізбегінің оң жағындағы у тізбегі.