Questions tagged [hypercomputation]
For questions about models of computation that can compute functions that Turing machines cannot. Often, these models are able to solve the halting problem.
23
questions
0
votes
0
answers
51
views
Is there a 4th barrier to computing?
I know there are three barriers of computation; the thermodynamic barrier, the light barrier and the quantum barrier. Let’s say we figure out how to send signals FTL, learn how to get rid of excess ...
- 1
-1
votes
2
answers
96
views
Is P vs NP, a paradox in a hypothetical perspective?
In a hypothetical scenario, where a precise and formal definition does not exist here, and thus expressed with analogies and verbal reasoning for the sake of simplifying the P, NP problem.
A(lan) ...
0
votes
1
answer
56
views
Using hypercomputation for "impossible" problems?
In mathematics and philosophy there are some unsolvable problems like Russell's paradox or the liar's paradox that are usually said to be undecidable... There are also other "impossibilities"...
- 101
-2
votes
2
answers
340
views
If the halting problem is NP hard, would P = NP with a hypercomputer capable of computing the halting problem in polynomial time?
The halting problem is NP hard, to my knowledge any NP problem can be reduced to a NP hard problem. Let us define a new computational complexity class called HP(Hypercomputational polynomal-time), The ...
- 219
0
votes
2
answers
217
views
Does allowing a mutable transition function in Turing machine make it more powerful?
as the title says does having a mutable transition function make the Turing machine more powerful
by mutable I mean we have a set of transition functions that we can choose one of them arbitrary based ...
user70365
1
vote
2
answers
115
views
The Church-Turing thesis and Hyper-computation
I am not a computer scientist and this is my first question.
This question is a question in layman terms and I also want the answer in layman terms.
When I searched hyper-computation. There was a list ...
- 113
0
votes
1
answer
117
views
Are Turing unrecognizable and undecidable languages, recognized and decided by hyper computation?
Do the hyper computing machines/models that are supposed to be more powerful than Turing machines, capable of recognizing and deciding the languages that are not recognizable/decidable by Turing ...
- 621
0
votes
2
answers
119
views
Is there any model of Game of Life compatible with hypercomputation?
I found a question in Mathematics Stack Exchange which asks a very similar question
(https://math.stackexchange.com/questions/1023812/hypercomputation-higher-dimensional-variants-of-conways-game-of-...
3
votes
1
answer
227
views
Is there a formal way of defining a Zeno Machine?
The idea of a Zeno machine is pretty interesting to me, but I can't seem to find a formal definition for how a Zeno machine would work. I can find a couple of definitions around but they are all ...
0
votes
0
answers
69
views
Can we see all of mathematics as an attempt to simplify computations?
This is a rather strong claim, and therefore likely to be incorrect, but hear me out.
Firstly, when I talk of “computations”, I mean this in a broader sense than normally used, because I am including ...
- 3,652
1
vote
2
answers
147
views
Would any continuous model of the universe have/be based on hypercomputational laws?
I've read that when Turing-Church thesis is applied to the universe and physics, one of the three interpretations that we can use and is defended by some important physicists is that:
"The universe ...
- 41
0
votes
1
answer
189
views
Would Schmidhuber's theories of everything be capable of performing hypercomputation?
Jürgen Schmidhuber pointed out that a simple explanation of the universe would be a Turing machine analogy programmed to execute all possible programs computing all possible histories for all types of ...
- 41
3
votes
1
answer
462
views
Can generalized Turing machines compute all reals?
Super-recursive algorithms are theoretical super-recursive algorithms are a generalization of ordinary algorithms that are more powerful, that is, compute more than Turing machines.
In this entry it ...
- 41
0
votes
0
answers
167
views
Church-Turing thesis and hypercomputation?
The Church-Turing is a hypothesis about the nature of computable functions. It states that a function on the natural numbers is computable by a human being following an algorithm, ignoring resource ...
- 41
0
votes
1
answer
120
views
Would hypercomputation machines be capable of simulating/computing/programming everything?
If uncomputable numbers existed, could this hypercomputation machines compute them? Could hypercomputation compute all types of uncomputable things? Even truly inconsistent things? Even things that ...
- 137
2
votes
2
answers
325
views
Can hypercomputation compute all kinds of incomputable numbers/functions/problems…etc?
Hypercomputation is a "cheat" that extends the capability of a Turing machine or quantum computer or cellular automaton by adding extra abilities. A standard method is "Oracle machines", Turing ...
- 137
6
votes
1
answer
1k
views
Do "Type-2" Turing machines with infinite length inputs have more computational power?
Certain idealizations of a Turing machine yield an increase in computational power, such as an inductive Turing machine, which can (trivially) solve the halting problem if it has an infinite amount of ...
- 837
18
votes
5
answers
5k
views
Turing machine + time dilation = solve the halting problem?
There are relativistic spacetimes (e.g. M-H spacetimes; see Hogarth 1994) where a worldline of infinite duration can be contained in the past of a finite observer. This means that a normal observer ...
- 283
9
votes
1
answer
203
views
Church-Turing and physical PDEs
When I read about the Church-Turing thesis it seems to be a common claim that "physical reality is Turing-computable." What is the basis for this claim? Are there any theoretical results along these ...
- 221
51
votes
4
answers
15k
views
Theoretical machines which are more powerful than Turing machines
Are there any theoretical machines which exceed Turing machines capability in at least some areas?
- 951
5
votes
0
answers
253
views
Computational power of Actor Model
In the question below, let TM be Turing machine, NTM be nondeterministic Turing machine and PTM be probabilistic Turing machine.
In his paper "Actor Model of Computation: Scalable Robust Information ...
- 51
1
vote
8
answers
548
views
Is infinitely fast computer fundamentally impossible even theoretically?
This may get slightly philosophical, but consider the following program:
...
- 153
1
vote
3
answers
341
views
Church-Turing thesis is a dualism
Church-Turing thesis : Every effectively calculable function is a TM-computable function.
But, hypercomputation models are strictly more powerful than TM and can solve TM-uncomputable problems on the ...
- 659