Macchina del Turing

Lumbard ucidental Quest articol chì l'è scrivuu in lombard, grafia milanesa.

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.

Modell de 'na Macchina del 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.

VariantModifiché

Macchina multibindellModifiché

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 deterministegaModifiché

  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 universalaModifiché

  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.

RiferimentModifiché

Vos corelaaModifiché