Hipercomputación

La hipercomputación o supercomputación de Turing és un conjunt de models de computació que poden proporcionar resultats que no són Turing-computables. Per eixemple, una màquina capaç de resoldre el problema de la parada seria un hiperordenador; també ho seria una que poguera evaluar correctament cada enunciat de l'aritmètica de Peano.

La tesis de Church-Turing afirma que qualsevol funció «computable» que puga ser calculada per un matemàtic en llapis i paper utilisant un conjunt finito d'algoritmes senzills, pot ser calculada per una màquina de Turing. Els hiperordenadores computen funcions que una màquina de Turing no pot i que, per tant, no són computables en el sentit de Church-Turing.

Tècnicament, l'eixida d'una màquina de Turing aleatòria no és computable; no obstant, la major part de la lliteratura sobre hipercomputación se centra en el càlcul de funcions determinista no aleatòries no computables.

Història

Alan Turing va introduir un model computacional que anava més allà de les màquines de Turing en la seua tesis doctoral de 1938 Systems of Logic Based on Ordinals.^[1] Este treball investigava sistemes matemàtics en els que es disponia d'un oràcul que podia calcular una única funció arbitrària (no recursiva) de naturals a naturals. Va utilisar este dispositiu per a demostrar que, inclús en eixos sistemes més potents, la indecidibilidad seguix present. Les màquines d'oràcul de Turing són abstracció matemàtiques i no són físicament realisables.^[2]

Models

Moltes propostes de hipercomputación consistixen en formes alternatives de llegir un oràcul o una funció d'assessorament integrada en una màquina clàssica. Unes atres permeten accedir a algun nivell superior de la jerarquia aritmètica. Per eixemple, les màquines de Turing supertarea, baix els supòsits habituals, serien capaços de calcular qualsevol predicat en el grau de la taula de veres que continga $Σ_{1}^{0}$ o $Π_{1}^{0}$ . L'excursió llimitadora, pel contrari, pot calcular qualsevol predicat o funció en el grau de Turing corresponent, que se sap que és $Δ_{2}^{0}$ . Gold va demostrar ademés que la recursividad parcial llimitadora permetria calcular precisament el grau de $Σ_{2}^{0}$ predicats.

Model	Predicats computables	Notes	Refs
supertarea	$tt (Σ_{1}^{0}, Π_{1}^{0})$	depén d'un observador extern	^[3]
llimitació/juí-i-error	$Δ_{2}^{0}$		^[4]^[5]
llimitació iterada (k voltes)	$Δ_{k + 1}^{0}$		^[6]
Màquina Blum-Shub-Smale		incomparables en les funcions reals computables tradicionals	^[7]
Espaciotiempo Malament-Hogarth	HYP	depén de l'estructura del espaciotiempo	^[8]
ret neuronal recurrent analògica	$Δ_{1}^{0} [f]$	f és una funció d'assessorament que dona pesos de conexió; el tamany està llimitat pel temps d'eixecució	^[9]^[10]
màquina de Turing de temps infinit	$A Q I$	Conjunts aritmètics cuasi inductivos	^[11]
màquina de Turing difusa clàssica	$Σ_{1}^{0} \cup Π_{1}^{0}$	per a qualsevol t-norma computable	^[12]
oràcul de funció creixent	$Δ_{1}^{1}$	per al model d'una seqüència; $Π_{1}^{1}$ són r.i.	^[13]

Vore també

Referències

↑ “Systems of Logic Based on Ordinals†” (1939). Proceedings of the London Mathematical Society 45: 161–228. doi:10.1112/plms/s2-45.1.161.
↑
↑ Petrus H. Potgieter. “Zeno machines and hypercomputation”. Theoretical Computer Science 358 (1): 23–33. doi:10.1016/j.tcs.2005.11.040.
↑ E. M. Gold (1965). “Limiting Recursion”. Journal of Symbolic Logic 30 (1): 28–48. doi:10.2307/2270580., E. Mark Gold (1967). “Language identification in the limit”. Information and Control 10 (5): 447–474. doi:10.1016/S0019-9958(67)91165-5.
↑ E. Mark Gold (1967). “Language identification in the limit”. Information and Control 10 (5): 447–474. doi:10.1016/S0019-9958(67)91165-5.
↑ L. K. Schubert. “Iterated Limiting Recursion and the Program Minimization Problem”. Journal of the ACM 21 (3): 436–445. doi:10.1145/321832.321841.
↑ Lenore, Blum; Felipe, Cuckel; Michael, Shub & Stephen, Smale (1998). Complexity and Real Computation (en en), Springer. ISBN 978-0-387-98281-6.
↑ P.D. Welch (2008). “The extent of computation in Malament-Hogarth spacetimes”. British Journal for the Philosophy of Science 59 (4): 659–674. doi:10.1093/bjps/axn031.
↑ H.T. Siegelmann. “Computation Beyond the Turing Limit”. Science 268: 545–548. doi:10.1126/science.268.5210.545. PMID 17756722. Bibcode: 1995Sci...268..545S.
↑ Hava Siegelmann (1994). “Analog Computation via Neural Networks”. Theoretical Computer Science 131 (2): 331–360. doi:10.1016/0304-3975(94)90178-3.
↑ P.D. Welch (2009). “Characteristics of discrete transfinite clave Turing machine models: Halting claves, stabilization claves, and Normal Form theorems”. Theoretical Computer Science 410 (4–5): 426–442. doi:10.1016/j.tcs.2008.09.050.
↑ Wiedermann, Jiří (2004). “Characterizing the super-Turing computing power and efficiency of classical fuzzy Turing machines”. Theoretical Computer Science 317 (1–3): 61–69. doi:10.1016/j.tcs.2003.12.004. “El seu (capacitat de resoldre el problema de detenció) es deu al seu criteri d'acceptació en el que s'assumix indirectament la capacitat de resoldre el problema de detenció.”
↑ Dmytro Taranovsky. «Finitism and Hypercomputation» (en en).

Referències

Este artícul conté una traducció derivada de «Hipercomputació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.

[1] “Systems of Logic Based on Ordinals†” (1939). Proceedings of the London Mathematical Society 45: 161–228. doi:10.1112/plms/s2-45.1.161.

[2] ↑

[3] Petrus H. Potgieter. “Zeno machines and hypercomputation”. Theoretical Computer Science 358 (1): 23–33. doi:10.1016/j.tcs.2005.11.040.

[LimRecurs-4] E. M. Gold (1965). “Limiting Recursion”. Journal of Symbolic Logic 30 (1): 28–48. doi:10.2307/2270580., E. Mark Gold (1967). “Language identification in the limit”. Information and Control 10 (5): 447–474. doi:10.1016/S0019-9958(67)91165-5.

[5] E. Mark Gold (1967). “Language identification in the limit”. Information and Control 10 (5): 447–474. doi:10.1016/S0019-9958(67)91165-5.

[IterLimRec-6] L. K. Schubert. “Iterated Limiting Recursion and the Program Minimization Problem”. Journal of the ACM 21 (3): 436–445. doi:10.1145/321832.321841.

[7] Lenore, Blum; Felipe, Cuckel; Michael, Shub & Stephen, Smale (1998). Complexity and Real Computation (en en), Springer. ISBN 978-0-387-98281-6.

[8] P.D. Welch (2008). “The extent of computation in Malament-Hogarth spacetimes”. British Journal for the Philosophy of Science 59 (4): 659–674. doi:10.1093/bjps/axn031.

[Siegelmann.1995-9] H.T. Siegelmann. “Computation Beyond the Turing Limit”. Science 268: 545–548. doi:10.1126/science.268.5210.545. PMID 17756722. Bibcode: 1995Sci...268..545S.

[10] Hava Siegelmann (1994). “Analog Computation via Neural Networks”. Theoretical Computer Science 131 (2): 331–360. doi:10.1016/0304-3975(94)90178-3.

[11] P.D. Welch (2009). “Characteristics of discrete transfinite clave Turing machine models: Halting claves, stabilization claves, and Normal Form theorems”. Theoretical Computer Science 410 (4–5): 426–442. doi:10.1016/j.tcs.2008.09.050.

[ClassicalFuzzy-12] Wiedermann, Jiří (2004). “Characterizing the super-Turing computing power and efficiency of classical fuzzy Turing machines”. Theoretical Computer Science 317 (1–3): 61–69. doi:10.1016/j.tcs.2003.12.004. “El seu (capacitat de resoldre el problema de detenció) es deu al seu criteri d'acceptació en el que s'assumix indirectament la capacitat de resoldre el problema de detenció.”

[Taranovsky-13] Dmytro Taranovsky. «Finitism and Hypercomputation» (en en).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]