Analysis of Capabilities
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 or . Limiting-recursion, by contrast, can compute any predicate or function in the corresponding Turing degree, which is known to be . Gold further showed that limiting partial recursion would allow the computation of precisely the predicates.
| Model | Computable predicates | Notes | Refs |
|---|---|---|---|
| supertasking | tt | dependent on outside observer | |
| limiting/trial-and-error | |||
| iterated limiting (k times) | |||
| Blum-Shub-Smale machine | incomparable with traditional computable real functions. | ||
| Malament-Hogarth spacetime | HYP | Dependent on spacetime structure | |
| Analog recurrent neural network | f is an advice function giving connection weights; size is bounded by runtime | ||
| Infinite time Turing machine | |||
| Classical fuzzy Turing machine | For any computable t-norm | ||
| Increasing function oracle | For the one-sequence model; are r.e. |
Read more about this topic: Hypercomputation
Famous quotes containing the words analysis and/or capabilities:
“Analysis as an instrument of enlightenment and civilization is good, in so far as it shatters absurd convictions, acts as a solvent upon natural prejudices, and undermines authority; good, in other words, in that it sets free, refines, humanizes, makes slaves ripe for freedom. But it is bad, very bad, in so far as it stands in the way of action, cannot shape the vital forces, maims life at its roots. Analysis can be a very unappetizing affair, as much so as death.”
—Thomas Mann (1875–1955)
“I maintain that I have been a Negro three times—a Negro baby, a Negro girl and a Negro woman. Still, if you have received no clear cut impression of what the Negro in America is like, then you are in the same place with me. There is no The Negro here. Our lives are so diversified, internal attitudes so varied, appearances and capabilities so different, that there is no possible classification so catholic that it will cover us all, except My people! My people!”
—Zora Neale Hurston (1891–1960)