Resultats de la cerca

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 cella…