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…

Com és usual en la història de les matemàtiques, té orígens aparentment molt diferents que finalment conflueixen i permeten d’establir el que esdevé una teoria enormement potent i irrenunciable Cal remarcar-ne el problema diofàntic plantejat per David Hilbert l’any 1900, i el problema de les paraules que sorgí en el món de la topologia algèbrica Es tracta de dos problemes típics de decidibilitat és a dir, aquells en què cal disposar d’un mètode que permeti de decidir una o altra de dues opcions atesa una equació diofàntica, té solució, són equivalents dues paraules donades per endavant L’any…

Dit més informalment, un conjunt X és recursiu quan existeix un algorisme que permet de decidir la resposta a la pregunta ' x ∈ X'

Dit més informalment, un conjunt X és recursivament enumerable si hi ha un algorisme que construeix el conjunt element a element