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]

The tag has no usage guidance.

3
votes
1answer
145 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 ...
8
votes
3answers
651 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, ...
1
vote
1answer
278 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?
5
votes
0answers
245 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. ...
0
votes
1answer
248 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 ...
17
votes
3answers
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 ...
16
votes
3answers
1k 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 ...
79
votes
10answers
13k 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 ...