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

Recentment s'han proposat models teòrics que pretenen refutar la tesi de Church, per exemple el de les [[ARNN]], que ha estat el més seriós. No obstant això no mostren l'efectivitat necessària, encara, per refutar amb arguments sòlids la tesi de Church. És clar que és més "fàcil" provar la falsedat de la tesi que la veritat de la mateixa. N'hi ha prou amb exposar un mètode efectiu o algorisme que no sigui Turing-computable. Això no és tan fàcil però és més "fàcil" de provar la veritat de la tesi, ja que sembla impossible negar la possibilitat lògica que sigui falsa. Hi ha una tesi relativitzada de Church-Turing que depèn dels graus de Turing definits per màquines de Turing amb oracles. Els oracles són mitjans formals que suposen que se li facilita certa informació a la màquina de Turing per a resoldre algun problema, això defineix una jerarquia que s'ha estudiat tant en la [[Teoria de la computabilitat|teoria de la computabilitat]] com en la [[Complexitat computacional|Teoria de la Complexitat]].

[[Categoria: Màquines de Turing]]

[[fa:تز چرچ-تورينگتورینگ]]