Editing Hypercomputation (section)

==="Infinite computational steps" models===
In order to work correctly, certain computations by the machines below literally require infinite, rather than merely unlimited but finite, physical space and resources; in contrast, with a Turing machine, any given computation that halts will require only finite physical space and resources.

A Turing machine that can ''complete'' infinitely many steps in finite time, a feat known as a [[supertask]]. Simply being able to run for an unbounded number of steps does not suffice. One mathematical model is the [[Zeno machine]] (inspired by [[Zeno's paradox]]). The Zeno machine performs its first computation step in (say) 1 minute, the second step in ½ minute, the third step in ¼ minute, etc.  By summing [[1/2 + 1/4 + 1/8 + 1/16 + ⋯|1&nbsp;+&nbsp;½&nbsp;+&nbsp;¼&nbsp;+&nbsp;...]] (a [[geometric series]]) we see that the machine performs infinitely many steps in a total of 2 minutes. According to [[Oron Shagrir]], Zeno machines introduce physical paradoxes and its state is logically undefined outside of one-side open period of [0, 2), thus undefined exactly at 2 minutes after beginning of the computation.<ref>These models have been independently developed by many different authors, including {{cite book|author=Hermann Weyl|  year=1927 | title=Philosophie der Mathematik und Naturwissenschaft| author-link=Hermann Weyl }}; the model is discussed in {{cite journal
 |author=[[Oron Shagrir|Shagrir, O.]]
 |title=Super-tasks, accelerating Turing machines and uncomputability 
 |journal= Theoretical Computer Science
 |date=June 2004 
 |pages=105–114 
 |doi=10.1016/j.tcs.2003.12.007 
 |volume=317 
 |issue=1–3 
 |doi-access=free 
 }}, {{cite journal| author=Petrus H. Potgieter| title=Zeno machines and hypercomputation| journal=Theoretical Computer Science| volume=358 | issue=1 |date=July 2006 | pages=23–33| doi=10.1016/j.tcs.2005.11.040| arxiv=cs/0412022| s2cid=6749770}} and {{cite journal
 |author=Vincent C. Müller 
 |title=On the possibilities of hypercomputing supertasks 
 |journal=Minds and Machines 
 |volume=21 
 |issue=1 
 |date=2011 
 |pages=83–96 
 |url=http://philpapers.org/rec/MLLOTP
 |doi=10.1007/s11023-011-9222-6
|citeseerx=10.1.1.225.3696 
 |s2cid=253434 
 }}</ref>

It seems natural that the possibility of time travel (existence of [[closed timelike curve]]s (CTCs)) makes hypercomputation possible by itself. However, this is not so since a CTC does not provide (by itself) the unbounded amount of storage that an infinite computation would require. Nevertheless, there are spacetimes in which the CTC region can be used for relativistic hypercomputation.<ref>{{Cite journal|arxiv = 1105.0047|doi = 10.1142/S0129626412400105|title = Closed Timelike Curves in Relativistic Computation|year = 2012|last1 = Andréka|first1 = Hajnal|last2 = Németi|first2 = István|last3 = Székely|first3 = Gergely|journal = Parallel Processing Letters|volume = 22|issue = 3|s2cid = 16816151}}</ref> According to a 1992 paper,<ref>{{Cite journal|doi = 10.1007/BF00682813|title = Does general relativity allow an observer to view an eternity in a finite time?|year = 1992|last1 = Hogarth|first1 = Mark L.|journal = Foundations of Physics Letters|volume = 5|issue = 2|pages = 173–181|bibcode = 1992FoPhL...5..173H|s2cid = 120917288}}</ref> a computer operating in a [[Malament–Hogarth spacetime]] or in orbit around a rotating [[black hole]]<ref>{{cite book | chapter=Can General Relativistic Computers Break the Turing Barrier? | author=István Neméti | author2=Hajnal Andréka | author2-link=Hajnal Andréka | title=Logical Approaches to Computational Barriers, Second Conference on Computability in Europe, CiE 2006, Swansea, UK, June 30-July 5, 2006. Proceedings | publisher=Springer | series=Lecture Notes in Computer Science | volume=3988 | doi=10.1007/11780342 | year=2006 | isbn=978-3-540-35466-6 | url-access=registration | url=https://archive.org/details/logicalapproache0000conf }}</ref> could theoretically perform non-Turing computations for an observer inside the black hole.<ref>{{Cite journal|arxiv = gr-qc/0104023|last1 = Etesi|first1 = Gabor|last2 = Nemeti|first2 = Istvan|title = Non-Turing computations via Malament-Hogarth space-times|journal = International Journal of Theoretical Physics|year = 2002|volume = 41|issue = 2|pages = 341–370|doi = 10.1023/A:1014019225365|s2cid = 17081866}}</ref><ref>{{Cite journal|doi = 10.1086/289716|title = Forever is a Day: Supertasks in Pitowsky and Malament-Hogarth Spacetimes|year = 1993|last1 = Earman|first1 = John|last2 = Norton|first2 = John D.|journal = Philosophy of Science|volume = 60|pages = 22–42|s2cid = 122764068}}</ref> Access to a CTC may allow the rapid solution to [[PSPACE-complete]] problems, a complexity class which, while Turing-decidable, is generally considered computationally intractable.<ref>{{Cite journal|arxiv = gr-qc/0209061|last1 = Brun|first1 = Todd A.|title = Computers with closed timelike curves can solve hard problems|journal = Found. Phys. Lett.|year = 2003|volume = 16|issue = 3|pages = 245–253|doi = 10.1023/A:1025967225931|s2cid = 16136314}}</ref><ref>[[Scott Aaronson|S. Aaronson]] and J. Watrous. Closed Timelike Curves Make Quantum and Classical Computing Equivalent [http://scottaaronson.com/papers/ctc.pdf]</ref>