Màquina de Turing
From Wikipedia, the free encyclopedia
La màquina de Turing és un model computacional introduït per Alan Turing en el treball "On computable numbers, with an application to the Entscheidungsproblem", publicat per la Societat Matemàtica de Londres, en el qual s'estudiava la qüestió plantejada per David Hilbert sobre si les matemàtiques són decidibles, és a dir, si hi ha un mètode definit que pugui aplicar-se a qualsevol sentència matemàtica i que resolgui si és certa o no. Turing va construir un model formal de computador, la màquina de Turing, un dispositiu que manipula símbols sobre una tira de cinta d'acord amb una taula de regles i va demostrar que existien problemes que una màquina no podia resoldre.[1][2]
Malgrat la seva simplicitat, la màquina de Turing pot ser adaptada per simular la lògica de qualsevol algorisme de computador i és particularment útil en l'explicació de les funcions d'una CPU dins d'un computador.
Originalment va ser definida com una «màquina automàtica» el 1936, a la revista Proceedings of the Societat Mathematics[3] de Londres. La màquina de Turing no està dissenyada com una tecnologia de computació pràctica, sinó com un dispositiu hipotètic que representa una màquina de computació, i van ajudar als científics a entendre els límits del càlcul mecànic.
Turing va donar una definició succinta de l'experiment en el seu assaig de 1948, «Màquines intel·ligents». Referint-se a la seva publicació de 1936, Turing va escriure que la màquina de Turing, aquí anomenada una màquina de computació lògica, consistia en:
« | ... una il·limitada capacitat de memòria obtinguda en la forma d'una cinta infinita marcada amb quadrats, en cadascun dels quals podria imprimir-se un símbol. En qualsevol moment hi ha un símbol a la màquina; anomenat el símbol llegit. La màquina pot alterar el símbol llegit i el seu comportament està en part determinat per aquest símbol, però els símbols en altres llocs de la cinta no afecten el comportament de la màquina. Tanmateix, la cinta es pot moure cap endavant i cap enrere a través de la màquina, essent això una de les operacions elementals de la màquina. Per tant qualsevol símbol a la cinta pot tenir finalment una oportunitat.[4] | » |
— Turing (1948, p. 61.) |
Una màquina de Turing que sigui capaç de simular qualsevol altra màquina de Turing és anomenada com una màquina universal de Turing (UTM, o simplement una màquina universal). Una definició més matemàticament orientada, amb una semblant naturalesa "universal", va ser presentada per Alonzo Church, el treball sobre el càlcul lambda s'entrellaça amb el de Turing en una teoria formal de la computació coneguda com la tesi de Church-Turing. La tesi assenyala que les màquines de Turing capturen, de fet, la noció informal d'un mètode eficaç en la lògica i les matemàtiques i proporcionen una definició precisa d'un algoritme o 'procediment mecànic'.
Estudiant les seves propietats abstractes, la màquina de Turing produeix moltes perspectives en les ciències de la computació i en la teoria de la complexitat.