Tesi de Church-Turing: diferència entre les revisions
Contingut suprimit Contingut afegit
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
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.
|