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 col·loquem n1 + 1 uns seguits d’un zero, després d’n2 + 1 uns seguits d’un zero,..., després nk + 1 uns seguits d’un zero i col·loquem la màquina en estat intern q0 i amb el cap lector en el zero que hi ha al darrere dels darrers nk + 1 uns. La resta de la cinta és plena de zeros. El zero significa que a la cel·la no hi ha res escrit. El nombre zero és designat amb un 1, l’u amb 11, el dos amb 111, etc. Aleshores la màquina OOO computa d’acord am el seu programa i s’ha d’esdevenir que, si OOOn1,...,nkOOO ∈ dom f i f(n1,...,nk) = y, la màquina s’atura i la situació final de la cinta és la mateixa que la inicial, però després del zero que segueix el bloc dels nk + 1 darrers uns, hi ha escrits y + 1 uns i el cap lector, quan la màquina s’atura, es troba en el zero que separa el darrer bloc d’uns inical del bloc nou d’uns. És a dir: si la situació inicial és
