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

Contingut suprimit Contingut afegit
m Bot: Traient 27 enllaços interwiki, ara proporcionats per Wikidata a d:q309157
m Corregit: fins el(s) -> fins al(s)
Línia 26:
Models equivalents a la màquina de Turing MT són: màquines de Turing amb una cinta infinita cap a una direcció, màquines de Turing amb una cinta infinita cap a les dues direccions, màquines de Turing amb múltiples cintes, màquines de Turing amb múltiples piles, màquines d'enumeració, entre d'altres.
 
Exemples de que la tesi de Church-Turing sembla veritable són molts, des del fet que tot algorisme és computable fins elal fet que fins i tot models teòrics que semblen molt més poderosos (i ho són però en altres sentits de complexitat), com ho és la computació quàntica, són reduïbles finalment a màquines de Turing. Tal com s'ha vist fins ara, els diferents intents directes o indirectes de crear models diferents a una màquina de Turing, tots són equivalents a màquines de Turing (o de menor poder computacional).
 
Els llenguatges que són acceptats per una màquina de Turing són exactament aquells generats per totes les [[Jerarquia de Chomsky|gramàtiques formals]]. El [[càlcul lambda]], per exemple, és una forma de definir funcions. Les funcions que poden ser computades amb el càlcul Lambda són exactament les que poden ser computades amb màquines de Turing. Aquests tres tipus, les màquines de Turing, les gramàtiques o llenguatges formals i el càlcul Lambda són molt diferents i van ser desenvolupats de manera aliena un de l'altre, però, són equivalents ja que tenen el mateix poder per resoldre problemes. Això generalment es pren com a evidència a favor de la tesi de Church-Turing.