Linked Questions

8
votes
0answers
346 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 ...
38
votes
8answers
16k 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 ...
39
votes
7answers
6k 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. ...
37
votes
3answers
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 ...
17
votes
3answers
2k 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 ...
7
votes
3answers
874 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, ...
4
votes
3answers
297 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 ...
4
votes
2answers
338 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 ...
9
votes
1answer
412 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
1answer
156 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 ...
0
votes
0answers
138 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 ...