Màquina de Zenón
En matemàtiques i ciències de la computació, les màquines de Zenón (també cridades màquines accelerades de Turing)[1] són un model computacional hipotètic relacionat en la màquina de Turing que permet realisar un número conjunt numerable de passos algorítmics en temps finito. Estes màquines estan descartades en la majoria dels models de computació.[2]
Més formalment, una màquina de Zenón és una màquina de Turing que requerix 2−n unitats de temps per a realisar la seua n-ésimo pas; per lo tant, el primer pas requerix 0.5 unitats de temps, el segon 0.25, el tercer 0.125 i aixina successivament, de modo que despuix d'una unitat de temps, s'haurà realisat un número de passos conjunt numerable (és dir, ℵ0).
L'idea de les màquines de Zenón va ser discutida per primera volta per Hermann Weyl en 1927; el nom es referix a les paradoxes de Zenón, atribuïdes al filòsof grec Zenón de Elea. Les màquines de Zenón eixerciten un paper crucial en algunes teories. La teoria del punt omega ideada pel físic Frank J. Tipler, per eixemple, solament pot ser vàlida si les màquines Zenón són possibles.
Màquines de Zenón i computabilidad
[editar | editar còdic]Les màquines de Zenón permetrien que es computaren algunes funcions que no són computables per mig de màquines de Turing. Per eixemple, el problema de la parada per a les màquines de Turing es pot resoldre en una màquina de Zenón (utilisant el següent algoritme escrit en pseudocódigo):
començar el programa escriga 0 en la primera posició de la cinta d'eixida; començar bucle simular 1 pas successiu de la màquina de Turing donada en l'entrada donada; si la màquina de Turing s'ha detingut, escriga 1 en la primera posició de la cinta d'eixida i trenque el cicle; bucle final programa final
El càlcul d'este tipo que va més allà del llímit de Turing es denomina hipercomputación, en este cas, hipercomputación a través d'una supertarea.
Vore també
[editar | editar còdic]- Hipercomputación
- Paradoxa de Ross-Littlewood
- Supertarea
- Llàntia de Thomson
- Punt Omega de Tipler
- Paradoxes de Zenón
Referències
[editar | editar còdic]- ↑ Hector Zenil (2013). A Computable Universe: Understanding and Exploring Nature as Computation, World Scientific, pp. 542 de 810. ISBN 9789814374309.
- ↑ Cris Calude, Gheorghe Paun (2000). Computing with Cells and Atoms: An Introduction to Quàntum, DNA and Membrane Computing, CRC Press, pp. 206 de 320. ISBN 9780748408993.
Referències
[editar | editar còdic]
- Este artícul conté una traducció derivada de «Máquina de Zenón» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.