Skip to main content
28 votes
Accepted

Turing machine + time dilation = solve the halting problem?

Note that Turing's proof is one of mathematics, not of physics. Within the model of a Turing machine Turing defined, undecidability of the halting problem has been proven and is a mathematical fact. ...
Discrete lizard's user avatar
  • 8,303
10 votes

Turing machine + time dilation = solve the halting problem?

The Turing machine is a formal mathematical model of computation, it does not answer to any physical limitations and does not care about relativistic effects. This means that Turing's proof does not ...
Ariel's user avatar
  • 13.4k
9 votes

Can generalized Turing machines compute all reals?

Any machine model in which a machine can be described by a string over a fixed alphabet can only compute countably many things. Since there are uncountably many real numbers, all of these machine ...
Yuval Filmus's user avatar
8 votes

Turing machine + time dilation = solve the halting problem?

Turing’s proof shows that no Turing machine can solve the Halting Problem no matter how much time you give it. If your spaceship used time dilation to give a computer a billion years to work, it ...
Davislor's user avatar
  • 1,241
7 votes
Accepted

Do "Type-2" Turing machines with infinite length inputs have more computational power?

Type-2 Turing machines are not more powerful than ordinary Turing machines in the sense that any map $\mathbb{N} \to \mathbb{N}$ that can be computed by a type-2 machine can also be computed by an ...
Andrej Bauer's user avatar
  • 30.9k
5 votes

Are Turing unrecognizable and undecidable languages, recognized and decided by hyper computation?

I see two ways of interpreting this question, but the answer is essentially trivial either way. Interpretation 1: Can every hypercomputation model decide some language that cannot be decided by a ...
Aaron Rotenberg's user avatar
5 votes

Turing machine + time dilation = solve the halting problem?

An objection is that you have defined a process that can produce infinite entropy in a compact region and that appears to do so in a finite segment of the observer's past. This means a few things ...
Eric Towers's user avatar
5 votes
Accepted

The Church-Turing thesis and Hyper-computation

The Church–Turing thesis is about physically realizable machines. To the best of our knowledge, hypercomputation models cannot be realized in the physical world. They are a figment of our imagination. ...
Yuval Filmus's user avatar
5 votes

Using hypercomputation for "impossible" problems?

Nope. Russell's paradox and the liar's paradox aren't undecidable. They aren't even decision problems. As far as we know, hypercomputers don't exist. They are an imaginary idea that don't appear ...
D.W.'s user avatar
  • 162k
4 votes

Is P vs NP, a paradox in a hypothetical perspective?

This makes no sense to me. You imagine a scenario that is self-contradictory, and then observe that it is a contradiction, and.. then what? All that proves is that your scenario can't happen. It's ...
D.W.'s user avatar
  • 162k
4 votes

Church-Turing and physical PDEs

The branch of mathematics and computer science that studies these questions is computable mathematics. The general answer is that things tend to be computable. I would add to that the observation that ...
Andrej Bauer's user avatar
  • 30.9k
4 votes

Can hypercomputation compute all kinds of incomputable numbers/functions/problems…etc?

It is a little hard to say for sure since since one has not found a final Theory Of Everything in physics. Mostly it seems that hypercomputation is physically impossible. On the other hand, an ...
Bjørn Kjos-Hanssen's user avatar
4 votes

Would hypercomputation machines be capable of simulating/computing/programming everything?

I think you have an important misunderstanding about what "uncomputable" means. It doesn't mean "doing something mathematically impossible", such as producing a non-trivial factorization of a prime ...
David Richerby's user avatar
3 votes

Is there a formal way of defining a Zeno Machine?

Hamkins' survey Infinite time Turing machines, linked by Yuval Filmus, formally defines a computational model (Infinite time Turing machine) that meets the requirements of a Zeno machine. The ...
Sriotchilism O'Zaic's user avatar
3 votes

Would any continuous model of the universe have/be based on hypercomputational laws?

If you are interested in the effect of being able to compute with continuous real numbers, you might enjoy learning about the Blum-Shub-Smale theory of computation with the reals. A good survey is ...
D.W.'s user avatar
  • 162k
2 votes

Can hypercomputation compute all kinds of incomputable numbers/functions/problems…etc?

Not only is hypercomputation believed to be physically impossible, but even more ambitiously, some people working at the intersection of physics and computer science think that P!=NP might be a ...
Aryeh's user avatar
  • 216
2 votes

Would any continuous model of the universe have/be based on hypercomputational laws?

It's a bit vague to talk about "models of universe". Let's stick to models of mathematics, as these are actually well understood. For example, we can ask about a topos (a model of a certain kind of ...
Andrej Bauer's user avatar
  • 30.9k
2 votes
Accepted

A paradox about cardinality of ALL and arithmetic hierarchies ― Did I just prove that ZFC is inconsistent?

No, you haven't proved ZFC inconsistent. Short version: try to actually define your generalized arithmetical hierarchy and it will become clear how things break down! The issue is that you've glossed ...
Noah Schweber's user avatar
1 vote
Accepted

If the halting problem is NP hard, would P = NP with a hypercomputer capable of computing the halting problem in polynomial time?

Assume a polynomial-time Halting Decider $H$ such that given the input string $\langle M, s \rangle$ it accepts if $M$ run on string $s$ halts in finite time, rejects otherwise, and completes this ...
kviiri's user avatar
  • 1,237
1 vote

If the halting problem is NP hard, would P = NP with a hypercomputer capable of computing the halting problem in polynomial time?

Since the halting problem is not computable, your hyper computer would be in violation of the laws of mathematics, and therefore capable of doing anything.
gnasher729's user avatar
  • 30.7k
1 vote

The Church-Turing thesis and Hyper-computation

I'll just address one model. WP says: The Zeno machine performs its first computation step in (say) 1 minute, the second step in ½ minute, the third step in ¼ minute, etc. By summing 1+½+¼+... (a ...
Jim Hefferon's user avatar
1 vote

Is there any model of Game of Life compatible with hypercomputation?

Cellular automata can be simulated with an ordinary Turing machine, so they don't have any more power than an ordinary Turing machine -- they can't perform "hypercomputation".
D.W.'s user avatar
  • 162k
1 vote

Would Schmidhuber's theories of everything be capable of performing hypercomputation?

If the hypothesis is that we live in a universe whose physics are computed by a Turing machine, then hypercomputation is trivially impossible in our universe. The constants you're taking about are ...
Daniel McLaury's user avatar
1 vote

Turing machine + time dilation = solve the halting problem?

Quote from Bangs, Crunches, Whimpers, and Shrieks: Thomson lamps, super $\pi$ machines, and Platonist computers are playthings of philosophers; they are able to survive only in the hothouse ...
Martín-Blas Pérez Pinilla's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible