Linked Questions
11 questions linked to/from What would it mean to disprove Church-Turing thesis?
7
votes
0
answers
378
views
Are there any models of computation currently being studied with the possibility of being more powerful than Turing Machines? [duplicate]
Possible Duplicate:
What would it mean to disprove Church-Turing thesis?
Are there any models of computation currently being studied with the possibility of being more powerful than Turing ...
- 283
41
votes
8
answers
19k
views
Why go to theoretical computer science/research?
I'm currently starting on the university [computer science] and there we have lot of opportunities to begin with researching. Before finding this website, I had no intention to go on this way [I ...
40
votes
7
answers
7k
views
Applicability of Church-Turing thesis to interactive models of computation
Paul Wegner and Dina Goldin have for over a decade been publishing papers and books arguing primarily that the Church-Turing thesis is often misrepresented in the CS Theory community and elsewhere. ...
- 835
38
votes
3
answers
6k
views
Extended Church-Turing Thesis
One of the most discussed questions on the site has been What it Would Mean to Disprove the Church-Turing Thesis. This is partly because Dershowitz and Gurevich published a proof of the Church-Turing ...
- 6,994
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 ...
- 19k
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
6
votes
3
answers
444
views
Why do people bring real-life Quantum Computing to the discussion of the Church-Turing thesis?
As an undergraduate with limited understanding of QC and even the C-T thesis, I have problems figuring out why in questions such as Extended Church-Turing Thesis real-life quantum stuff is even given ...
- 183
4
votes
2
answers
373
views
Simulation of every physical quantum system on quantum computer
Let me quote from the section 9.3 of Classical and Quantum Computation by Kitaev, Shen and Vyalyi.
With high confidence, we may claim that every physical quantum system
can be efficiently ...
- 831
9
votes
1
answer
416
views
What is the proper role of verification in quantum sampling, simulation, and extended-Church-Turing (E-C-T) testing?
Since no answer was given, a flag has been set requesting that this question be converted to a community wiki.
The comments by Aaron Sterling, Sasho Nikolov, and Vor have been synthesized into the ...
-2
votes
1
answer
172
views
Is there a mathematical definition of algorithm? [closed]
A friend of mine usually talks to me about Church's thesis. Some days ago I found a proof and talked about it to him. He said that "it's possible to prove the thesis using an arbitrary definition of ...
- 105
0
votes
0
answers
163
views
mathematical study of the 'Church-Turing thesis'
The Church-Turing thesis postulates that essentially all models of computation -Turing machines, Post systems, lambda-definability etc yield the same class of computable functions. Now we can think of ...
