Snip

An attempt to understand the notion better led Robin Gan... student and friend) in 1980 to analyze machine computati... humancomputation acted out by a Turing machine). Gandy'... and analysis of, "cellular automata", "Conway's game of ... "parallelis


Categories 


For Snip 
loading snip actions ... 

For Page 
loading url actions ... 
HTML 
An attempt to understand the notion better led <a href="/wiki/Robin_Gandy" title="Robin Gandy">Robin Gandy</a> (Turing's student and friend) in 1980 to analyze <i>machine</i> computation (as opposed to humancomputation acted out by a Turing machine). Gandy's curiosity about, and analysis of, "cellular automata", "Conway's game of life", "parallelism" and "crystalline automata" led him to propose four "principles (or constraints) ... which it is argued, any machine must satisfy."<sup id="_ref26" class="reference"><a href="#_note26" title="">[30]</a></sup> His mostimportant fourth, "the principle of causality" is based on the "finite velocity of propagation of effects and signals; contemporary physics rejects the possibility of instaneous action at a distance."<sup id="_ref27" class="reference"><a href="#_note27" title="">[31]</a></sup> 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 IIV is computable 
