Pagkakaiba sa mga pagbabagong ng "Makinang Turing"

m
walang buod ng pagbabago
m
m
 
:...walang hanggang kakayahan ng [[memorya]] na makakamit sa anyong ng isang walang hanggang tape na minarkhan bilang mga [[parisukat]] na sa bawat isa ay maaaring tatakan ng isang simbolo. Sa anumang pagkakataon, meron lamang isang simbolo sa makina na tinatawag na binasang(scanned) simbolo. Maaaring baguhin ng makina ang binasang simbol at ang pag-aasal nito ay sa isang bahagi matutukoy ng simbolong ito ngunit ang mga simbolo sa tape sa iba pang lugar ay hindi nakakaapekto sa pag-aasal ng makina. Gayunpaman, ang tape ay maaaring muling pabalikin at pasulungin sa makina na ito isa sa mga pangunahing operasyon ng makina. Kaya ang anumang simbolo sa tape ay sa kalaunan may pagkakataon(innings). (Turing 1948, p. 61)
 
Ang isang makinang Turing na may kakayahang gumaya sa anumang iba pang makinang Turing ay tinatwag na pangkalahatang makinang Turing(Turing machine o UTM o universal machine). Ang isang mas matematikal na depinisyon na may kaparehong "pangkalahatan(unibersal)" na kalikasan ay ipinakilala ni [[Alonzo Church]] na ang kanyang akda sa [[kalkulong lambda]] ay kaugnay ng gawa ni TUring sa isang pormal na [[teoriya ng komputasyon]] na kilala bilang [[tesis na Church-Turing]]. Ang tesis na ito ay nagsasaad na ang mga makinang Turing ay talagang nabibihag ang inpormal na nosyon ng epektibong paraan sa [[lohika]] at [[matematika]] at nagbibigay ng tiyak na depinisyon ng [[algoritmo]] o mekanikal na hakbang. Ang pag-aaral ng mga abstraktong katangian nito ay nagbibigay ng maaraming mga pagkaunawa sa [[agham pangkompyuter]] at [[teoriyateorya ng kompleksidadkomputasyonal na komplehidad]].
 
==Impormal na depinisyon==
11,186

edits