Teoria de la computabilitat: diferència entre les revisions
Contingut suprimit Contingut afegit
m Removing Link GA template (handled by wikidata) |
m Arreglats links i afegides referències |
||
Línia 1:
La '''teoria de la computabilitat''' és la part de la [[computació]] que estudia els [[Problema de decisió|problemes de decisió]] que poden ser resolts amb un [[algorisme]] o equivalentment amb una [[màquina de Turing]].<ref>{{Ref-llibre|títol=Theory of computation|url=https://www.worldcat.org/oclc/694056|editorial=Wiley|data=[1974]|lloc=New York,|isbn=0-471-09585-0|cognom=Brainerd, Walter S.}}</ref><ref>{{Ref-publicació|article=On Computable Numbers, with an Application to the Entscheidungsproblem|url=https://londmathsoc.onlinelibrary.wiley.com/doi/abs/10.1112/plms/s2-42.1.230|publicació=Proceedings of the London Mathematical Society|data=1937|issn=1460-244X|pàgines=230–265|volum=s2-42|exemplar=1|doi=10.1112/plms/s2-42.1.230|llengua=en|nom=A. M.|cognom=Turing}}</ref><ref>{{Ref-llibre|edició=2nd ed|títol=The universal Turing machine : a half-century survey|url=https://www.worldcat.org/oclc/32013506|editorial=Springer-Verlag|data=1995|lloc=Wien|isbn=3-211-82637-8}}</ref> La teoria de la computabilitat s'interessa per quatre preguntes:
* Quins problemes pot resoldre una màquina de Turing?
* Quins altres formalismes equivalen a les màquines de Turing?
Línia 7:
== Quins problemes pot resoldre una màquina de Turing?==
No tots els problemes poden ser resolts. Un [[
* L'[[Entscheidungsproblem]] (problema de decisió en [[alemany]]) que es defineix com: donada una frase del [[càlcul de predicats de primer ordre]], decidir si és un teorema. [[Alonzo Church]] i [[Alan Turing]] demostraren independentment que aquest problema és indecidible.
* El [[Problema de la parada]], que es defineix així: donat un programa i la seva entrada, decidir si aquest programa acabarà per aquesta entrada o si correrà indefinidament. [[Alan Turing]] va demostrar que és un problema indecidible.
Línia 15:
Els [[Llenguatge formal|llenguatges formals]] que són acceptats per una màquina de Turing són exactament aquells que poden ser generats per una [[gramàtica formal]]. El [[Càlcul lambda]] és una forma de definir funcions. Les funcions que poden ser computades amb el càlcul Lambda són exactament aquelles que poden ser computades amb una màquina de Turing. Aquests tres formalismes, les màquines de Turing, els llenguatges formals i el càlcul Lambda són formalismes molt dissímils i van ser desenvolupats per diferents persones. Tot i això, tots tres són equivalents i tenen el mateix poder d'expressió. Generalment es pren aquesta coincidència com evidència de què la [[Tesi de Church-Turing]] és certa, que l'afirmació de què la noció intuïtiva d'algorisme o procediment efectiu de còmput correspon a la noció de còmput en una màquina de Turing.
Els [[Ordinador|computadors electrònics]], basats en l'[[Arquitectura de von Neumann|arquitectura Von Neumann]] així com les [[Computació quàntica|màquines quàntiques]] tindrien exactament el mateix poder d'expressió que el d'una màquina de Turing si disposés de recursos il·limitats de temps i espai. Com a conseqüència, els [[llenguatge de programació|llenguatges de programació]] tenen com a molt el mateix poder d'expressió que el dels programes per una màquina de Turing i a la pràctica no tots hi arriben. Els llenguatges amb poder d'expressió equivalent al d'una màquina de Turing s'anomenen [[
Entre els formalismes equivalents a una màquina de Turing hi ha:
Línia 22:
* Màquines de Turing amb nombre limitat d'estats i símbols per a la cinta.
* Màquina de Turing amb només dos estats.
*
* Autòmats finits amb dos contadors
* [[Gramàtica formal|Gramàtiques formals]]
Línia 31:
* [[Autòmat cel·lular|Autòmats cel·lulars]]
* El [[joc de la vida]] de [[John Conway]]
*
* [[Màquina de Turing probabilística|Màquines de Turing probabilístiques]]
* [[Computació quàntica|Computador quàntic]]
Línia 40:
Es considera que algunes màquines tenen un major poder que les màquines de Turing. Per exemple, una [[màquina oracle]] que utilitza una caixa negra que pot calcular la funció particular que no és calculable amb una màquina de Turing. La força de còmput d'una màquina oracle ve descrita pel seu [[grau de Turing]]. La [[teoria de còmputs reals]] estudia màquines amb precisió absoluta en els nombres reals. Dins d'aquesta teoria, és possible demostrar afirmacions interessants, tals com el "el complement d'un [[conjunt de Mandelbrot]] és només parcialment decidible".
== Referències ==
{{Referències}}
{{ORDENA:Teoria De La Computabilitat}} <!--ORDENA generat per bot-->
| |||