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.
26 questions
4
votes
1
answer
719
views
Are oracle machines for the halting problem just impossible to build but logically valid, or are they also introducing logical inconsistencies?
On Wikipedia in the article for oracle machines it says the following:
A machine with an oracle for the halting problem can determine whether
particular Turing machines will halt on particular inputs,...
- 55
0
votes
0
answers
35
views
Is Homomorphic Computation Possible Using Graph Theory
Homomorphic encryption allows to store data on a blockchain encrypted, but a smart contract is a program that is executed on a node on the blockchain, therefore the "source code" of the ...
2
votes
1
answer
178
views
A paradox about cardinality of ALL and arithmetic hierarchies ― Did I just prove that ZFC is inconsistent?
This problem arose when I tried to find the arithmetic hierarchy that $\mathsf{ALL}$, the class of all formal languages over a finite alphabet, corresponds to (like how $\mathsf{R} = \Delta^0_1$ and $\...
- 391
0
votes
0
answers
77
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
173
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
314
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"...
- 105
-2
votes
2
answers
731
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 ...
- 239
0
votes
2
answers
378
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
212
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
147
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 ...
- 641
0
votes
2
answers
178
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
316
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
135
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 ...
- 4,284
1
vote
2
answers
250
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
285
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
651
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
256
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
216
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 ...
- 135
1
vote
2
answers
453
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 ...
- 135
7
votes
1
answer
2k
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 ...
- 1,081
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
278
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
17k
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?
- 961
5
votes
0
answers
312
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
762
views
Is infinitely fast computer fundamentally impossible even theoretically?
This may get slightly philosophical, but consider the following program:
...
- 153
1
vote
3
answers
473
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 ...
- 671