Tyuring mashinası túsinigi qansha ulıwmalıq ózgeshelikine iye?

Tyuring tezisi. Tyuring mashinası algoritm túsinigin

anıqlawdıń bir jolin kórsetedi. Sol sebepli bir neshe sorawlar payda

boladı :

- Tyuring mashinası túsinigi qansha ulıwmalıq ózgeshelikine iye?

- algoritmlami Tyuring mashinası quralı menen beriw usılın universal

usıl dep bola ma?

- hámme algoritmlami sol usıl menen beriw múmkinbe?

Bul sorawlarǵa házirgi waqıtta ámeldegi bolǵan algoritmlar teoriyası

tómendegi gipoteza menen juwap beredi: hár qanday algoritmdı Tyuring

funksional sxeması arqalı beriw hám uyqas Tyuring mashinasında realizatsiya

etiw (ámelge asırıw ) múmkin.

Bul gipoteza Tyuring tezisi dep ataladı. Onı tastıyıqlaw múmkin emes,

sebebi bul tezis qatań tariyplanmagan algoritm túsinigin qatań

anıqlanǵan Tyuring mashinası túsinigi menen baylanıstıradı.

Bul tezisti biykarlaw etiw ushın Tyuring mashinasında realizatsiyalan-

maydigan (ámelge asırılmaytuǵın ) algoritm bar ekenligin kórsetiw

kerek. Biraq házirge shekem anıqlanǵan hámme algoritmlami Tyuring

funksional sxeması arqalı realizatsiya etiw múmkin.

7. 7. 2. Ekvivalent túsinikler. Sonı da aytıp ótemizki,

Markovning normal algoritm túsinigi hám de Chyorch, Gyodel hám

Klini tárepinen kiritilgen rekursiv algoritm hám rekursiv funksiya

túsinikleri, uyqas túrde, Tyuring tárepinen kiritilgen algoritm

túsinigi hám Tyuring funksional sxeması menen ekvivalentligi iyis-

botlangan.

Bul dálil óz gezeginde Tyuring gipotezasining tuwrılıǵın taǵı bir

ret tastıyıqlaydı.