Resultats de la cerca

Procedeix de la següent manera elemental A cada cella de la cinta hom pot escriure un 0 o un 1 Aleshores, la màquina de Turing, segons l’estat intern de la capsa negra i del símbol que llegeix el cap lector, pot pendre una de les cinc decisions següents 1, escriure un zero a la cella llegida pel cap lector, esborrant abans el que pugui haver-hi escrit 2, escriure un 1 a la cella, esborrant abans el que pugui haver-hi escrit 3, donar un pas cap a la dreta 4, donar un pas cap a l’esquerra 5, aturar-se Una màquina de Turing és, doncs, una matriu com ara…

Una funció f A ⊑ ℕ n → ℕ és computable si, i només si, existeix un algorisme formal, com ara una màquina de Turing que la computa Quan diem, però, que una funció k -ària f A ⊑ ℕ k → ℕ és computable per mitjà d’una màquina de Turing OOO La idea és la següent a la cinta de la màquina colloquem n 1 + 1 uns seguits d’un zero, després d’n 2 + 1 uns seguits d’un zero,, després n k + 1 uns seguits d’un zero i colloquem la màquina en estat intern q 0 i amb el cap lector en el zero que hi ha al darrere dels darrers n k + 1 uns La resta de la cinta és plena de zeros El zero significa que a la …