Editing Hypercomputation (section)

==Analysis of capabilities==
Many hypercomputation proposals amount to alternative ways to read an [[oracle machine|oracle]] or [[advice (complexity)|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 reduction|truth-table degree]] containing <math>\Sigma^0_1</math> or <math>\Pi^0_1</math>. Limiting-recursion, by contrast, can compute any predicate or function in the corresponding [[Turing degree]], which is known to be <math>\Delta^0_2</math>. Gold further showed that limiting partial recursion would allow the computation of precisely the <math>\Sigma^0_2</math> predicates.

{| class="wikitable sortable"
|-
! Model
! Computable predicates
! Notes
! {{Refh}}
|-
| supertasking
| <math>\operatorname{tt}\left(\Sigma^0_1, \Pi^0_1\right)</math>
| dependent on outside observer
| <ref>{{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}}</ref>
|-
| limiting/trial-and-error
| <math> \Delta^0_2 </math>
| 
| <ref name=LimRecurs/>
|-
| iterated limiting (''k'' times)
| <math> \Delta^0_{k+1} </math>
| 
| <ref name=IterLimRec/>
|-
| [[Blum–Shub–Smale machine]]
|  
| incomparable with traditional [[computable real]] functions
| <ref>{{cite book|author=[[Lenore Blum]], Felipe Cucker, Michael Shub, and [[Stephen Smale]]|title=Complexity and Real Computation|title-link= Complexity and Real Computation |isbn=978-0-387-98281-6|year=1998|publisher=Springer }}</ref>
|-
| [[Malament–Hogarth spacetime]]
| '''[[Hyperarithmetic hierarchy|HYP]]'''
| dependent on spacetime structure
| <ref>{{cite journal | author=P.D. Welch | title = The extent of computation in Malament-Hogarth spacetimes | arxiv=gr-qc/0609035 | journal=British Journal for the Philosophy of Science |volume=59 | issue = 4 |year= 2008 | pages=659–674 | doi=10.1093/bjps/axn031| author-link = P.D. Welch }}</ref>
|-
|-
| analog recurrent neural network
| <math> \Delta^0_1[f] </math>
| ''f'' is an advice function giving connection weights; size is bounded by runtime
| <ref name="Siegelmann.1995">{{cite journal | doi=10.1126/science.268.5210.545 | pmid=17756722 | url=http://binds.cs.umass.edu/papers/1995_Siegelmann_Science.pdf | author=H.T. Siegelmann | title=Computation Beyond the Turing Limit | journal=Science | volume=268 | number=5210 | pages=545–548 | date=Apr 1995 | bibcode=1995Sci...268..545S | s2cid=17495161 }}</ref><ref>{{cite journal | author=Hava Siegelmann | author2=Eduardo Sontag | title=Analog Computation via Neural Networks | journal=Theoretical Computer Science | volume=131 | year=1994 | pages=331–360 | doi=10.1016/0304-3975(94)90178-3 | issue=2 | author-link2=Eduardo Sontag| author-link=Hava Siegelmann | doi-access=free }}</ref>
|-
| infinite time Turing machine
| <math> AQI</math>
| Arithmetical Quasi-Inductive sets
|  <ref>{{cite journal|author=P.D. Welch |title=Characteristics of discrete transfinite time Turing machine models: Halting times, stabilization times, and Normal Form theorems |journal=Theoretical Computer Science |year=2009 |volume=410 |issue=4–5 |pages=426–442 |doi=10.1016/j.tcs.2008.09.050  |author-link=P.D. Welch |doi-access=free }}</ref>
|-
| classical fuzzy Turing machine
| <math> \Sigma^0_1 \cup \Pi^0_1 </math>
| for any computable [[T-norm fuzzy logics|t-norm]]
| <ref name=ClassicalFuzzy />
|-
| increasing function oracle
| <math> \Delta^1_1 </math>
| for the one-sequence model; <math> \Pi^1_1 </math> are r.e.
| <ref name=Taranovsky/>
|-
| ordinal turing machine
| <math> \Delta^1_2 </math>
| for the parameter-free model
| <ref>{{cite journal |doi=10.3233/COM-2012-002 |title=Tree Representations via Ordinal Machines |date=2012 |last1=Schlicht |first1=Philipp |last2=Seyfferth |first2=Benjamin |journal=Computability |volume=1 |pages=45–57 }}</ref>
|}