Tesi de Church-Turing: diferència entre les revisions

Altres màquines equivalents a una màquina de Turing inclouen: màquines de Turing amb més d'una cinta, màquines de Turing amb cintes n-dimensionals, màquines de Turing amb un nombre limitat d'estats i símbols, autòmats finits amb dues piles, autòmats finits amb dos comptadors, gramàtica formal, sistema Post, càlcul Lambda, funcions recursives parcials, autòmats cel·lulars (el joc de la vida de Conway o l'autòmat cel ·lular amb una dimensió, dos estats, tres cel per veí i la regla 110), màquines de Turing probabilistes , màquines de Turing no deterministes i computadores quàntiques (els tres últims exemples utilitzen una Definició lleugerament diferent d'acceptació de llenguatge, ja que accepten una cadena si hi ha tan sols un còmput que l'accepta o la majoria l'accepta i aleshores és equivalent a màquina de Turing) .