Stiamo lavorando per ripristinare l'app di Unionpedia nel Google Play Store
UscenteArrivo
🌟Abbiamo semplificato il nostro design per una migliore navigazione!
Instagram Facebook X LinkedIn

Teorema di Church

Indice Teorema di Church

Il teorema di Church, dimostrato dal matematico Alonzo Church, nel 1936, afferma che la logica predicativa è indecidibile. In realtà, è quasi un corollario della soluzione di Alan Turing al problema della fermata, uno dei 23 problemi di Hilbert.

Indice

  1. 3 relazioni: Paradosso, Tesi di Church-Turing, Turing equivalenza.

Paradosso

Un paradosso, nopunti, è, genericamente, la descrizione di un fatto che contraddice l'opinione comune o l'esperienza quotidiana, riuscendo perciò sorprendente, straordinaria o bizzarra; più precisamente, in senso logico-linguistico, indica sia un ragionamento che appare invalido, ma che deve essere accettato, sia un ragionamento che appare corretto, ma che porta a una contraddizione.

Vedere Teorema di Church e Paradosso

Tesi di Church-Turing

Nella teoria della calcolabilità la tesi di Church-Turing è un'ipotesi che afferma: «Se un problema è umanamente calcolabile, allora esisterà una macchina di Turing in grado di risolverlo (cioè di calcolarlo)».

Vedere Teorema di Church e Tesi di Church-Turing

Turing equivalenza

La Turing equivalenza è la proprietà dei modelli di calcolo che hanno lo stesso potere computazionale di una macchina di Turing universale (MdTu).

Vedere Teorema di Church e Turing equivalenza