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
- Bountied 0
- Unanswered
- Frequent
- Score
- Trending
- Week
- Month
- Unanswered (my tags)
4
votes
1
answer
664
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,...
0
votes
0
answers
21
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
144
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 $\...
0
votes
0
answers
64
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
votes
2
answers
150
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
165
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"...
-2
votes
2
answers
654
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 ...
0
votes
2
answers
330
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 ...
user avatar
user70365
1
vote
2
answers
184
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 ...
0
votes
1
answer
128
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 ...
0
votes
2
answers
147
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
282
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
103
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 ...
1
vote
2
answers
205
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 ...
0
votes
1
answer
246
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 ...