تحسيب فائق

التحسيب الفائق (الإنكليزية: Hypercomputation) هو مصطلح يشير إلى نماذج التحسيب المختلفة عن آلة تورنگ. هذا يتضمن العديد من طرق التحسيب النظرية للتوابع الغير قابلة للتحسيب وفق آلة تورنگ باستخدام خوارزميات عودية فائقة super-recursive algorithm (انظر مهمة فائقة). وهو يشمل أيضاً أشكالاً عديدة من التحسيب، كالتحسيب التفاعلي. استخدم المصطلح لأول مرة من عام 1999 من قبل جاك كوبلاند Jack Copeland وديان برودفوت Diane Proudfoot.^[1]

التاريخ

A computational model going beyond Turing machines was introduced by Alan Turing in his 1938 PhD dissertation Systems of Logic Based on Ordinals.^[2] This paper investigated mathematical systems in which an oracle was available, which could compute a single arbitrary (non-recursive) function from naturals to naturals. He used this device to prove that even in those more powerful systems, undecidability is still present. Turing's oracle machines are mathematical abstractions, and are not physically realizable.^[3]

فضاء الحالة

In a sense, most functions are uncomputable: there are $ℵ_{0}$ computable functions, but there are an uncountable number ( $2^{ℵ_{0}}$ ) of possible super-Turing functions.^[4]

المناذج

Hypercomputer models range from useful but probably unrealizable (such as Turing's original oracle machines), to less-useful random-function generators that are more plausibly "realizable" (such as a random Turing machine).

تحليل القدرات

Many hypercomputation proposals amount to alternative ways to read an oracle or advice function embedded into an otherwise classical machine. Others allow access to some higher level of the arithmetic hierarchy. For example, supertasking Turing machines, under the usual assumptions, would be able to compute any predicate in the truth-table degree containing $Σ_{1}^{0}$ or $Π_{1}^{0}$ . Limiting-recursion, by contrast, can compute any predicate or function in the corresponding Turing degree, which is known to be $Δ_{2}^{0}$ . Gold further showed that limiting partial recursion would allow the computation of precisely the $Σ_{2}^{0}$ predicates.

النموذج	Computable predicates	ملاحظات	Ref.
supertasking	$t t (Σ_{1}^{0}, Π_{1}^{0})$	dependent on outside observer	^[5]
limiting/trial-and-error	$Δ_{2}^{0}$		^[6]
iterated limiting (k times)	$Δ_{k + 1}^{0}$		^[7]
Blum–Shub–Smale machine		incomparable with traditional computable real functions	^[8]
Malament–Hogarth spacetime	HYP	dependent on spacetime structure	^[9]
analog recurrent neural network	$Δ_{1}^{0} [f]$	f is an advice function giving connection weights; size is bounded by runtime	^[10]^[11]
infinite time Turing machine	$A Q I$	Arithmetical Quasi-Inductive sets	^[12]
classical fuzzy Turing machine	$Σ_{1}^{0} \cup Π_{1}^{0}$	for any computable t-norm	^[13]
increasing function oracle	$Δ_{1}^{1}$	for the one-sequence model; $Π_{1}^{1}$ are r.e.	^[14]
ordinal turing machine	$Δ_{2}^{1}$	for the parameter-free model	^[15]

انظر أيضاً

مراجع

^ Copeland and Proudfoot, Alan Turing's forgotten ideas in computer science. Scientific American, April 1999.
^ Turing, A. M. (1939). "Systems of Logic Based on Ordinals†". Proceedings of the London Mathematical Society. 45: 161–228. doi:10.1112/plms/s2-45.1.161. hdl:21.11116/0000-0001-91CE-3.
^ "Let us suppose that we are supplied with some unspecified means of solving number-theoretic problems; a kind of oracle as it were. We shall not go any further into the nature of this oracle apart from saying that it cannot be a machine" (Undecidable p. 167, a reprint of Turing's paper Systems of Logic Based On Ordinals)
^ J. Cabessa; H.T. Siegelmann (Apr 2012). "The Computational Power of Interactive Recurrent Neural Networks" (PDF). Neural Computation. 24 (4): 996–1019. CiteSeerX 10.1.1.411.7540. doi:10.1162/neco_a_00263. PMID 22295978. S2CID 5826757.
^ Petrus H. Potgieter (July 2006). "Zeno machines and hypercomputation". Theoretical Computer Science. 358 (1): 23–33. arXiv:cs/0412022. doi:10.1016/j.tcs.2005.11.040. S2CID 6749770.
^ خطأ استشهاد: وسم <ref> غير صحيح؛ لا نص تم توفيره للمراجع المسماة LimRecurs
^ خطأ استشهاد: وسم <ref> غير صحيح؛ لا نص تم توفيره للمراجع المسماة IterLimRec
^ Lenore Blum, Felipe Cucker, Michael Shub, and Stephen Smale (1998). Complexity and Real Computation. Springer. ISBN 978-0-387-98281-6.{{cite book}}: CS1 maint: multiple names: authors list (link)
^ P.D. Welch (2008). "The extent of computation in Malament-Hogarth spacetimes". British Journal for the Philosophy of Science. 59 (4): 659–674. arXiv:gr-qc/0609035. doi:10.1093/bjps/axn031.
^ H.T. Siegelmann (Apr 1995). "Computation Beyond the Turing Limit" (PDF). Science. 268 (5210): 545–548. Bibcode:1995Sci...268..545S. doi:10.1126/science.268.5210.545. PMID 17756722. S2CID 17495161.
^ Hava Siegelmann; Eduardo Sontag (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 time Turing machine models: Halting times, stabilization times, and Normal Form theorems". Theoretical Computer Science. 410 (4–5): 426–442. doi:10.1016/j.tcs.2008.09.050.
^ خطأ استشهاد: وسم <ref> غير صحيح؛ لا نص تم توفيره للمراجع المسماة ClassicalFuzzy
^ خطأ استشهاد: وسم <ref> غير صحيح؛ لا نص تم توفيره للمراجع المسماة Taranovsky
^ Schlicht, Philipp; Seyfferth, Benjamin (2012). "Tree Representations via Ordinal Machines". Computability. 1: 45–57. doi:10.3233/COM-2012-002.

قراءة إضافية

Martin Davis, Why there is no such discipline as hypercomputation, Applied Mathematics and Computation, Volume 178, Issue 1, 1 July 2006, Pages 4-7, Special Issue on Hypercomputation
Mike Stannett, The case for hypercomputation, Applied Mathematics and Computation, Volume 178, Issue 1, 1 July 2006, Pages 8-24, Special Issue on Hypercomputation
Alan Turing, Systems of logic based on ordinals, Proc. London math. soc., 45, 1939
Hava Siegelmann. Neural Networks and Analog Computation: Beyond the Turing Limit Boston: Birkhäuser.
Hava Siegelmann. The simple dynamics of super Turing theories; Theoretical Computer Science Volume 168, Issue 2, 20 November 1996, Pages 461-472.
Keith Douglas. Super-Turing Computation: a Case Study Analysis (PDF), M.S. Thesis, Carnegie Mellon University, 2003.
L. Blum, F. Cucker, M. Shub, S. Smale, Complexity and Real Computation, Springer-Verlag 1997. General development of complexity theory for abstract machines that compute on real numbers instead of bits.
On the computational power of neural nets
Toby Ord. Hypercomputation: Computing more than the Turing machine can compute: A survey article on various forms of hypercomputation.
Apostolos Syropoulos (2008), Hypercomputation: Computing Beyond the Church-Turing Barrier (preview), Springer. ISBN 9780387308869
Burgin, M. S. (1983) Inductive Turing Machines, Notices of the Academy of Sciences of the USSR, v. 270, No. 6, pp. 1289-1293
Mark Burgin (2005), Super-recursive algorithms, Monographs in computer science, Springer. ISBN 0387955690
Cockshott, P. and Michaelson, G. Are there new Models of Computation? Reply to Wegner and Eberbach, The computer Journal, 2007
Copeland, J. (2002) Hypercomputation, Minds and machines, v. 12, pp. 461-502
Martin Davis (2006), "The Church–Turing Thesis: Consensus and opposition". Proceedings, Computability in Europe 2006. Lecture notes in computer science, 3988 pp. 125–132
Hagar, A. and Korolev, A., Quantum Hypercomputation – Hype or Computation?, (2007)
Rogers, H. (1987) Theory of Recursive Functions and Effective Computability, MIT Press, Cambridge Massachusetts
Volkmar Putz and Karl Svozil, Can a computer be "pushed" to perform faster-than-light?, (2010)

روابط خارجية

الكلمات الدالة:

آلة تورنگ

[1] Copeland and Proudfoot, Alan Turing's forgotten ideas in computer science. Scientific American, April 1999.

[2] Turing, A. M. (1939). "Systems of Logic Based on Ordinals†". Proceedings of the London Mathematical Society. 45: 161–228. doi:10.1112/plms/s2-45.1.161. hdl:21.11116/0000-0001-91CE-3.

[3] "Let us suppose that we are supplied with some unspecified means of solving number-theoretic problems; a kind of oracle as it were. We shall not go any further into the nature of this oracle apart from saying that it cannot be a machine" (Undecidable p. 167, a reprint of Turing's paper Systems of Logic Based On Ordinals)

[4] J. Cabessa; H.T. Siegelmann (Apr 2012). "The Computational Power of Interactive Recurrent Neural Networks" (PDF). Neural Computation. 24 (4): 996–1019. CiteSeerX 10.1.1.411.7540. doi:10.1162/neco_a_00263. PMID 22295978. S2CID 5826757.

[5] Petrus H. Potgieter (July 2006). "Zeno machines and hypercomputation". Theoretical Computer Science. 358 (1): 23–33. arXiv:cs/0412022. doi:10.1016/j.tcs.2005.11.040. S2CID 6749770.

[LimRecurs-6] خطأ استشهاد: وسم <ref> غير صحيح؛ لا نص تم توفيره للمراجع المسماة LimRecurs

[IterLimRec-7] خطأ استشهاد: وسم <ref> غير صحيح؛ لا نص تم توفيره للمراجع المسماة IterLimRec

[8] Lenore Blum, Felipe Cucker, Michael Shub, and Stephen Smale (1998). Complexity and Real Computation. Springer. ISBN 978-0-387-98281-6.{{cite book}}: CS1 maint: multiple names: authors list (link)

[9] P.D. Welch (2008). "The extent of computation in Malament-Hogarth spacetimes". British Journal for the Philosophy of Science. 59 (4): 659–674. arXiv:gr-qc/0609035. doi:10.1093/bjps/axn031.

[Siegelmann.1995-10] H.T. Siegelmann (Apr 1995). "Computation Beyond the Turing Limit" (PDF). Science. 268 (5210): 545–548. Bibcode:1995Sci...268..545S. doi:10.1126/science.268.5210.545. PMID 17756722. S2CID 17495161.

[11] Hava Siegelmann; Eduardo Sontag (1994). "Analog Computation via Neural Networks". Theoretical Computer Science. 131 (2): 331–360. doi:10.1016/0304-3975(94)90178-3.

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

[ClassicalFuzzy-13] خطأ استشهاد: وسم <ref> غير صحيح؛ لا نص تم توفيره للمراجع المسماة ClassicalFuzzy

[Taranovsky-14] خطأ استشهاد: وسم <ref> غير صحيح؛ لا نص تم توفيره للمراجع المسماة Taranovsky

[15] Schlicht, Philipp; Seyfferth, Benjamin (2012). "Tree Representations via Ordinal Machines". Computability. 1: 45–57. doi:10.3233/COM-2012-002.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]