Accions

Diferència entre revisions de la pàgina «Màquina de Turing»

De Wikisofia

m (bot: - cap a endavant o enrere + cap endavant o cap enrere)
m (bot: - o, el que + o, cosa que)
 
(Hi ha 4 revisions intermèdies del mateix usuari que no es mostren)
Línia 1: Línia 1:
 
{{ConcepteWiki}}
 
{{ConcepteWiki}}
 
[[File:turing.gif|thumb|Alan M. Turing]]
 
[[File:turing.gif|thumb|Alan M. Turing]]
Procediment «mecànic» idealitzat, això és, procediment que seguiria una màquina ideal, descompost en les seves parts elementals i inventat pel matemàtic anglès [[Autor:Turing, Alan Mathison|Alan Turing]] (1912-1954) com a resposta a l'anomenat [[decisió, problema de la|problema de decisió]], proposat en 1900 per [[Autor:Hilbert, David|David Hilbert]], al Congrés nacional de matemàtics a París. Aquest problema plantejava si era possible trobar un procediment algorítmic, o un procediment mecànic, que resolgués, en principi, tots els problemes de matemàtiques. Turing va dissenyar (1937) aquesta màquina ideal com un dispositiu constituït per un autòmat i una cinta (potencialment) infinita, dividida en caselles amb símbols o en blanc, i un dispositiu capaç de llegir el contingut de cada casella, esborrar o imprimir símbols, i de desplaçar-se cap endavant o cap enrere (o esquerra i dreta), de manera que, efectuats tots els càlculs, la màquina es parés i donés el resultat final. El resultat al fet que va arribar, més o menys al mateix temps que [[Autor:Church, Alonzo|Alonzo Church]], que havia treballat en el mateix problema d'Hilbert de forma independent, és que: 1) una màquina de Turing és un algorisme; 2) si una màquina de Turing resol un problema és que aquest és computable; 3) no existeix un algorisme general per a tot problema matemàtic o, el que és el mateix, no per a tot problema la màquina de Turing s'atura, o no tot problema és computable. Si a aquestes conclusions s'hi afegeix que la ment humana pot considerar-se una màquina de Turing, tenim la denominada [[tesi de Church-Turing|tesi de Church-Turing]].
+
Procediment «mecànic» idealitzat, és a dir, procediment que seguiria una màquina ideal, descompost en les seves parts elementals i inventat pel matemàtic anglès [[Autor:Turing, Alan Mathison|Alan Turing]] (1912-1954) com a resposta a l'anomenat [[decisió, problema de la|problema de decisió]], proposat en 1900 per [[Autor:Hilbert, David|David Hilbert]], al Congrés nacional de matemàtics a París. Aquest problema plantejava si era possible trobar un procediment algorítmic, o un procediment mecànic, que resolgués, en principi, tots els problemes de matemàtiques. Turing va dissenyar (1937) aquesta màquina ideal com un dispositiu constituït per un autòmat i una cinta (potencialment) infinita, dividida en caselles amb símbols o en blanc, i un dispositiu capaç de llegir el contingut de cada casella, esborrar o imprimir símbols, i de desplaçar-se cap endavant o cap enrere (o esquerra i dreta), de manera que, efectuats tots els càlculs, la màquina es parés i donés el resultat final. El resultat a què va arribar, més o menys al mateix temps que [[Autor:Church, Alonzo|Alonzo Church]], que havia treballat en el mateix problema de Hilbert de forma independent, és que: 1) una màquina de Turing és un algorisme; 2) si una màquina de Turing resol un problema, és que aquest és computable; 3) no existeix un algorisme general per a tot problema matemàtic o, cosa que és el mateix, no per a tot problema la màquina de Turing s'atura, o no tot problema és computable. Si a aquestes conclusions s'hi afegeix que la ment humana pot considerar-se una màquina de Turing, tenim la denominada [[tesi de Church-Turing|tesi de Church-Turing]].
  
 
Es denomina «màquina universal de Turing» a la màquina de Turing capaç de solucionar tot problema computable. Els computadors digitals actuals es consideren màquines d'aquest tipus.
 
Es denomina «màquina universal de Turing» a la màquina de Turing capaç de solucionar tot problema computable. Els computadors digitals actuals es consideren màquines d'aquest tipus.

Revisió de 14:59, 3 nov 2018



Alan M. Turing

Procediment «mecànic» idealitzat, és a dir, procediment que seguiria una màquina ideal, descompost en les seves parts elementals i inventat pel matemàtic anglès Alan Turing (1912-1954) com a resposta a l'anomenat problema de decisió, proposat en 1900 per David Hilbert, al Congrés nacional de matemàtics a París. Aquest problema plantejava si era possible trobar un procediment algorítmic, o un procediment mecànic, que resolgués, en principi, tots els problemes de matemàtiques. Turing va dissenyar (1937) aquesta màquina ideal com un dispositiu constituït per un autòmat i una cinta (potencialment) infinita, dividida en caselles amb símbols o en blanc, i un dispositiu capaç de llegir el contingut de cada casella, esborrar o imprimir símbols, i de desplaçar-se cap endavant o cap enrere (o esquerra i dreta), de manera que, efectuats tots els càlculs, la màquina es parés i donés el resultat final. El resultat a què va arribar, més o menys al mateix temps que Alonzo Church, que havia treballat en el mateix problema de Hilbert de forma independent, és que: 1) una màquina de Turing és un algorisme; 2) si una màquina de Turing resol un problema, és que aquest és computable; 3) no existeix un algorisme general per a tot problema matemàtic o, cosa que és el mateix, no per a tot problema la màquina de Turing s'atura, o no tot problema és computable. Si a aquestes conclusions s'hi afegeix que la ment humana pot considerar-se una màquina de Turing, tenim la denominada tesi de Church-Turing.

Es denomina «màquina universal de Turing» a la màquina de Turing capaç de solucionar tot problema computable. Els computadors digitals actuals es consideren màquines d'aquest tipus.