Entrades

S'estan mostrant les entrades d'aquesta data: de setembre 6, 2023

No existeix un algorisme per generar tots els algorismes.

Teorema. Donat una entrada e i una sortida po no existeix cap algorisme per trobar tots els dm's tals que la màquina de Turing T compleix que T(e,dm)=po. Demostració. Hem vist al missatge immediata anteriorment publicat que aquest algorisme tendria el problema de que no es pot decidir a priori si una màquina de Turing s'aturarà o no. Com que l'algorisme utilitza les màquines de Turing aquest algorisme no podem sebre si s'aturarà. El que si podem fer és posar un límit de temps d'execució a les màquines de Turing i trobar-ne molts.