Questions tagged [hypercomputation]
The hypercomputation tag has no usage guidance.
8 questions
4
votes
1
answer
210
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 ...
- 149
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, ...
- 301
1
vote
1
answer
359
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?
- 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.
...
- 151
1
vote
1
answer
329
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 ...
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 ...
- 293
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 ...
- 19.2k
97
votes
10
answers
21k
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 ...
user200