Macchina del Turing
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.
Variant
ModifegaMacchina multibindell
ModifegaLa macchina del Turing multibindell a l'è compagna de quèlla classega la ma la gh'ha pussee bindell e donca la gh'ha la possibilità de scernì, in la soa tabella, che bindell moeuv e in su che bindell legg e scriv.
Macchina minga deterministega
Modifega
|
Per savenn pussee, varda l'articol Macchina del Turing minga deterministega. |
La macchina del Turing minga deterministega la permètt de 'vègh on parallelism degià che in la presenza del midemm stat la permett pussee transizion.
Macchina universala
Modifega|
|
Per savenn pussee, varda l'articol Macchina del Turing universala. |
La macchina del Turing universala a l'è 'na macchina del Turing bona de simulà tucc i alter macchin del Turing.