Name
Abstract | ||
|---|---|---|
The Church-Turing Thesis has been the subject of many variations and interpretations over the years. Specifically, there are versions that refer only to functions over the natural numbers (as Church and Kleene did), while others refer to functions over arbitrary domains (as Turing intended). Our purpose is to formalize and analyze the thesis when referring to functions over arbitrary domains. First, we must handle the issue of domain representation. We show that, prima facie, the thesis is not well defined for arbitrary domains, since the choice of representation of the domain might have a non-trivial influence. We overcome this problem in two steps: (1) phrasing the thesis for entire computational models, rather than for a single function; and (2) proving a "completeness" property of the recursive functions and Turing machines with respect to domain representations. In the second part, we propose an axiomatization of an "effective model of computation" over an arbitrary countable domain. This axiomatization is based on Gurevich's postulates for sequential algorithms. A proof is provided showing that all models satisfying these axioms, regardless of underlying data structure, are of equivalent computational power to, or weaker than, Turing machines. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1007/978-3-540-78127-1_12 | Pillars of Computer Science |
Keywords | Field | DocType |
entire computational model,church-turing thesis,equivalent computational power,turing machine,non-trivial influence,effective model,natural number,arbitrary countable domain,domain representation,arbitrary domain,data structure,church turing thesis,satisfiability,computer model | μ-recursive function,Discrete mathematics,Church–Turing thesis,Universal Turing machine,Algebra,Super-recursive algorithm,Turing reduction,Description number,Turing machine,Halting problem,Mathematics | Conference |
Volume | ISSN | ISBN |
4800 | 0302-9743 | 3-540-78126-9 |
Citations | PageRank | References |
13 | 0.71 | 10 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Udi Boker | 1 | 141 | 16.24 |
| Nachum Dershowitz | 2 | 2818 | 473.00 |