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.

Filter by
Sorted by
Tagged with
0 votes
0 answers

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 ...
Max's user avatar
  • 1
-1 votes
2 answers

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) ...
Jeremy Shiklov's user avatar
0 votes
1 answer

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"...
vengaq's user avatar
  • 101
-2 votes
2 answers

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 ...
Colonizor48's user avatar
0 votes
2 answers

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
1 vote
2 answers

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 ...
Rounak Sarkar's user avatar
0 votes
1 answer

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 ...
al pal's user avatar
  • 621
0 votes
2 answers

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 (
user180164's user avatar
3 votes
1 answer

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 ...
Sriotchilism O'Zaic's user avatar
0 votes
0 answers

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 ...
user56834's user avatar
  • 3,652
1 vote
2 answers

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 ...
sztorwi's user avatar
  • 41
0 votes
1 answer

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 ...
sztorwi's user avatar
  • 41
3 votes
1 answer

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 ...
sztorwi's user avatar
  • 41
0 votes
0 answers

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 ...
sztorwi's user avatar
  • 41
0 votes
1 answer

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 ...
bautzeman's user avatar
  • 137
2 votes
2 answers

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 ...
bautzeman's user avatar
  • 137
6 votes
1 answer

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 ...
Mike Battaglia's user avatar
18 votes
5 answers

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 ...
K--'s user avatar
  • 283
9 votes
1 answer

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 ...
user168715's user avatar
51 votes
4 answers

Theoretical machines which are more powerful than Turing machines

Are there any theoretical machines which exceed Turing machines capability in at least some areas?
user1561358's user avatar
5 votes
0 answers

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 ...
Paul Sujkov's user avatar
1 vote
8 answers

Is infinitely fast computer fundamentally impossible even theoretically?

This may get slightly philosophical, but consider the following program: ...
Eiver's user avatar
  • 153
1 vote
3 answers

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 ...
François's user avatar
  • 659