Editing Church–Turing thesis (section)

=== Later developments ===
An attempt to better understand the notion of "effective computability" led [[Robin Gandy]] (Turing's student and friend) in 1980 to analyze ''machine'' computation (as opposed to human-computation acted out by a Turing machine). Gandy's curiosity about, and analysis of, [[cellular automata]] (including [[Conway's game of life]]), parallelism, and crystalline automata, led him to propose four "principles (or constraints)&nbsp;... which it is argued, any machine must satisfy".<ref>{{harvcolnb|Gandy|1980|pages=123ff.}}</ref> His most-important fourth, "the principle of causality" is based on the "finite velocity of propagation of effects and signals; contemporary physics rejects the possibility of instantaneous action at a distance".<ref>{{harvcolnb|Gandy|1980|page=135}}</ref> From these principles and some additional constraints—(1a) a lower bound on the linear dimensions of any of the parts, (1b) an upper bound on speed of propagation (the velocity of light), (2) discrete progress of the machine, and (3) deterministic behavior—he produces a theorem that "What can be calculated by a device satisfying principles I–IV is computable."<ref>{{harvcolnb|Gandy|1980|page=126}}</ref>

In the late 1990s [[Wilfried Sieg]] analyzed Turing's and Gandy's notions of "effective calculability" with the intent of "sharpening the informal notion, formulating its general features axiomatically, and investigating the axiomatic framework".<ref>Sieg 1998–1999 in {{harvcolnb|Sieg|Sommer|Talcott|2002|pages=390ff.}}; also {{harvcolnb|Sieg|1997|pp=154ff.}}</ref> In his 1997 and 2002 work Sieg presents a series of constraints on the behavior of a ''computor''—"a human computing agent who proceeds mechanically". These constraints reduce to:

*"(B.1) (Boundedness) There is a fixed bound on the number of symbolic configurations a computor can immediately recognize.
*"(B.2) (Boundedness) There is a fixed bound on the number of internal states a computor can be in.
*"(L.1) (Locality) A computor can change only elements of an observed symbolic configuration.
*"(L.2) (Locality) A computor can shift attention from one symbolic configuration to another one, but the new observed configurations must be within a bounded distance of the immediately previously observed configuration.
*"(D) (Determinacy) The immediately recognizable (sub-)configuration determines uniquely the next computation step (and id [instantaneous description])"; stated another way: "A computor's internal state together with the observed configuration fixes uniquely the next computation step and the next internal state."<ref>In a footnote Sieg breaks Post's 1936 (B) into (B.1) and (B.2) and (L) into (L.1) and (L.2) and describes (D) differently. With respect to his proposed [[Gandy machine]] he later adds LC.1, LC.2, GA.1 and GA.2. These are complicated; see Sieg 1998–1999 in {{harvcolnb|Sieg|Sommer|Talcott|2002|pages=390ff.}}</ref>

The matter remains in active discussion within the academic community.<ref>A collection of papers can be found in {{harvtxt|Olszewski|Woleński|Janusz|2006}}. Also a review of this collection: {{cite web |author-first=Peter |author-last=Smith |date=2007-07-11 |title=Church's Thesis after 70 Years |url=http://www.logicmatters.net/resources/pdfs/CTT.pdf}}</ref><ref>See also {{cite web |url=http://www.turing.org.uk/publications/ct70.pdf |title=Did Church and Turing Have a Thesis about Machines? |last=Hodges |first=Andrew |date=2005 |access-date=2014-07-27 |archive-url=https://web.archive.org/web/20160304032827/http://www.turing.org.uk/publications/ct70.pdf |archive-date=2016-03-04 |url-status=dead}}</ref>