Modell:Savevet/3
La macchina del Turing a l'è 'n modell matematich de calcol che 'l reppresenta 'na macchina astratta che la manipola i dacc in su 'n bindell, potenzialment infinii, a segonda di regoll de 'na tabella. Anca se l'è 'n modell assee semplis, daa on algoritm informategh la se pò costruì semper la relativa macchina del Turing, per la tesi de Church-Turing.
La lavora in su 'n bindell infinii dividuu in cell discrett e 'na testina la legg on caratter, ciappaa de 'n alfabett giamò deciduu prima, e a segonda del caratter el decid se spostà el bindell, se scriv on noeuv caratter, cambià de stat o fermà la computazion.
L'è stada teorizzada in del 1936 de l'Alan Turing per parlà del problema de la decidibilità.
La completezza Turing a l'è l'abilità de 'n sistema de istruzion de emulà 'na macchina del Turing, on lenguagg Turing complett a l'è bon de fà tucc i compit che se pòden dà a 'n computer, foeura che per la memoria finida.
(Va inanz)