Linked Questions

8
votes
0answers
328 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 ...
-1
votes
0answers
40 views

Can we prove that anything that programming languages can do, Turing machines can do? [duplicate]

From Church-Turing thesis we can infer that anything that programming language can do, Turing machine can. So I wanted to know whether we can prove it somehow and if we can, how we can do it?
38
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. ...
35
votes
8answers
14k 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 ...
35
votes
3answers
5k 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 ...
8
votes
3answers
725 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
2answers
327 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
385 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
153 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
125 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 ...