Skip to main content
OverflowAI is here! AI power for your Stack Overflow for Teams knowledge community. Learn more

Questions tagged [hypercomputation]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
3 votes
1 answer
198 views

What is the Turing degree of Kleene's O?

It's not computable whether a number is a member of Kleene's ${\mathcal {O}}$. What is that set's Turing degree? I can almost see an argument that ${\mathcal {O}} \leq_T \emptyset^{(2)}$ but I can't ...
Paul Crowley's user avatar
7 votes
3 answers
1k views

Misunderstanding the Church-Turing thesis?

My understanding of the Church-Turing thesis is the: It puts a limit on what can be computed by any discrete and finite process. Although still a thesis, not a theorem, if it were to be disproven, ...
Alexander S King's user avatar
1 vote
1 answer
355 views

Does hyper-computational power of infinite time Turing machines also require infinite memory?

Can a infinite time Turing machine perform hyper-computation like checking the consistency of the set theory ZF without using infinite memory?
Inducto's user avatar
  • 27
5 votes
0 answers
284 views

What language does Zeno machines recognize?

A Zeno machine of order 1 is a Turing machine that uses half the time it ran its $(n-1)$th step to run its nth step, hence can run infinite steps in just 2 seconds. This is called one step of order 1. ...
user2249675's user avatar
1 vote
1 answer
316 views

What's the nature of hypercomputing and relativity?

Somewhere I read something like "a hypercomputer rotating around a rotating black hole" would have some esoteric properties e.g. would produce other answers than other hypercomputers and other ...
Niklas Rosencrantz's user avatar
19 votes
3 answers
2k views

Why has hypercomputation research died down?

I see a lot of research on hypercomputation in the 1990's, but in more recent years there seems to be little work on the topic. Is it true that research in this area has died down? If so, what could ...
Velvet Ghost's user avatar
20 votes
3 answers
3k views

How do models of hypercomputation overcome the Halting Problem?

Hypercomputation refers to models of computation that are not possible to simulate using Turing machines. (Hypercomputers are not necessarily physically realisable!) Some hypercomputers have access ...
András Salamon's user avatar
96 votes
9 answers
20k views

What would it mean to disprove Church-Turing thesis?

Sorry for the catchy title. I want to understand, what should one have to do to disprove the Church-Turing thesis? Somewhere I read it's mathematically impossible to do it! Why? Turing, Rosser etc ...
user avatar