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 
 Macchina multibindell 
La 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 

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 

La macchina del Turing universala a l'è 'na macchina del Turing bona de simulà tucc i alter macchin del Turing.

 Riferiment 
Le Macchine di Turing
Macchine di Turing non deterministiche 
Macchine di Turing 
Macchina di Turing universale 

 Vos corelaa  
Programmazion imperativa
Architettura de Von Neumann
Architettura Harvard
BlooP e FlooP
Problema de la fermada
Macchina minga organizzada
Macchina a stat finii
Ipercomputazion

Categoria:Teoria de l'informazzion