0
$\begingroup$

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 a much wider class of models of computation including dynamical systems, DNA and molecular models, quantum computers, chemical reactions, etc.

  1. Can we regard the notion of computation as analogous to that of an abstract group and in analogy to Cayley theorem of group theory (every group can be realized as a subgroup of a permutation group), a computation as a realization in a particular model. More abstractly, the realization of computation in any of the different models is similar to the notion of group representation, in which the same abstract group can be realized variously as a group of linear automorphisms of a chosen linear space. Is this view of computation correct or reasonable?

  2. Why does (or should) a mathematical structure carry a generic computation? Just as symmetries of physical systems give rise to conservation laws in physics (Noether's theorem), are there analogs in this setting?

  3. How do we determine whether a mathematical structure has a rich or poor computational structure?

  4. How is the notion of computation supported in each structure? Is it always carried in the same way? I am looking for ideas in analogy to that of 'configuration space' or phase space in a dynamical system which has the structure of a symplectic manifold and is the cotangent bundle of the dynamical system enabling the Hamiltonian formulation of dynamics (which holds uniformly for classical as well as quantum mechanics)

  5. Are there any possible approaches towards a mathematical proof (or disproof) of the 'Church-Turing thesis'?

Improve this question
$\endgroup$
  • 2
    $\begingroup$ This question and its answers and comments might help you, also this blog post. $\endgroup$ – Artem Kaznatcheev♦ May 1 '14 at 12:50
  • $\begingroup$ all Turing complete systems are equivalent, anything less than that has less power but does not suffice for computation in general. as my college teachers stated, the thesis is named a thesis (& not a theorem) because it cant be proven. there is some attempt to "go beyond" the thesis in the theory of interactive computation (and some other misc ideas eg "hypercomputation") but its considered questionable/fringe by mainstream TCS researchers. $\endgroup$ – vzn May 1 '14 at 20:16
  • $\begingroup$ a) you should focus on one question per post. b) ad 5: there is no formal model of "intuitive computability" so it is impossible to prove the C-T-thesis. $\endgroup$ – Raphael May 4 '14 at 9:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.