Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

0
votes
1answer
32 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 ...
1
vote
2answers
148 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 ...
4
votes
1answer
561 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 ...
16
votes
5answers
4k 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 ...
8
votes
1answer
142 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 ...
35
votes
4answers
7k 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?
5
votes
0answers
185 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 ...
2
votes
7answers
196 views

Is infinitely fast computer fundamentally impossible even theoretically?

This may get slightly philosophical, but consider the following program: ...
2
votes
3answers
226 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 ...