Church-Turing Theses Variants
The Church-Turing Theses
Oron Shagrir
HEPIC seminar, March 2021
The claim:
There are different variants of the Church-Turing theses (CTT):
•
CTT-original: refers to what (most of) the founders said
•
CTT-algorithm: refer to what (most) computer science textbooks say.
•
Physicality theses (modest, bold, super-bold): Refer to physical systems.
Based on: Copeland and Shagrir, CACM 2019; chapters 2-3 of my
The Nature
of Physical Computation
, OUP (forthcoming).
C
T
T
-
O
r
i
g
i
n
a
l
(
C
T
T
-
O
)
•
“We now define the notion, already discussed, of an effectively
calculable function of positive integers by identifying it with the
notion of a recursive function of positive integers (or of a λ-definable
function of positive integers)” (Church 1936: 100).
•
CTT-O
:
Every function that can be effectively computed (by an
idealized human computer) is Turing computable.
What is effective?
Gödel used the terms
mechanical procedure
and
finite
procedure:
Mechanical: “
The outstanding feature of the rules of inference being
that they are purely formal, i.e., refer only to the outward structure of
the formulas, not to their meaning” (Gödel 1933: 45).
Finite
: The computation is subject to finiteness constraints, explicated
in Turing’s analysis of human computers (Turing 1936).
What is the source of finiteness?
•
Cognitive approach: The finiteness constraints reflect the upper
limitations on humans’ cognitive-calculative capacities.
•
Non-cognitive approach: The finiteness constraints reflect the use
(epistemic role) of computation in the context of logic and
mathematics.
(Copeland and Shagrir 2013).
C
T
T
-
A
l
g
o
r
i
t
h
m
(
C
T
T
-
A
)
•
“The claim, called
Church’s thesis
or the
Church-Turing thesis
, is a
basis for the equivalence of algorithmic procedures and computing
machines” (Nagin and Impagliazzo 1995: 611).
•
CTT-A: Any function that can be algorithmically computed by a
machine is Turing computable.
What is an algorithm?
•
Turing assumed that “a human being can only write one symbol at a
time,” and this assumption cannot be carried over to a parallel
machine that “prints an arbitrary number of symbols simultaneously”
(Gandy 1980: 124–5).
•
“In addition to classical sequential algorithms, in use from antiquity,
we have now parallel, interactive, distributed, real-time, analog,
hybrid, quantum, etc. algorithms.” (Gurevich 2012: 32)… “none of the
other known kinds of algorithms seem to threaten the thesis” (p. 33).
Physical vs. algorithmic computation
•
Algorithmic computation need not be “physical” or even “physically
realizable”: Moschovakis and Paschalis say that their approach adopts
“a very abstract notion of algorithm that takes recursion as a primitive
operation and is so wide as to admit ‘non-implementable’ algorithms”
(2008: 87).
•
Physical computation need not be “finite” in the algorithmic sense: It
allows infinitely many steps within a terminating computation
(supertasks).
T
h
e
p
h
y
s
i
c
a
l
C
h
u
r
c
h
-
T
u
r
i
n
g
T
h
e
s
i
s
(
P
C
T
T
)
•
Wolfram formulated “a physical form of the Church-Turing
hypothesis”:
•
[U]niversal computers are as powerful in their computational capacities as
any physically realizable system can be, so that they can simulate any physical
system. (Wolfram 1985: 735)
•
Deutsch describes “the physical version of the Church-Turing
principle”:
•
Every finitely realizable physical system can be perfectly simulated by a
universal model computing machine operating by finite means”
(Deutsch
1985: 99).
The physical Church-Turing Thesis (PCTT)
[T]he Physical Church-Turing Thesis … is the conjecture
that whatever physical computing device (in the
broader sense) or physical thought-experiment will be
designed by any future civilization, it will always be
simulateable by a Turing machine. (Andréka, Németi,
and Németi 2009: 500)
The modest and the bold (Piccinini 2011)
•
The Modest Physical Church-Turing Thesis (PCTT-M):
Every function
computed by a physical system is Turing computable.
•
The Bold Physical Church-Turing Thesis (PCTT-B
)
Every physical system can
be simulated to any specified degree of accuracy by a universal Turing
machine.
•
The bold versions proposed in the literature are often "logically
independent of one another", and exhibit "lack of confluence" (Piccinini
2011: 747-748)
Pour-El and Richards against PCTT-B
•
Pour-El and Richards (1981) showed that the familiar three-
dimensional wave equation produces non-Turing-computable output
sequences for some Turing computable input sequences.
•
They also gave an example where the solution to the wave equation
maps computable sequences of reals to computable sequences of
reals, but the mapping itself is not
effectively
uniformly continuous.
•
It is controversial whether the requisite input sequences properly
encode all the relevant information (Weihrauch and Zhong 2002;
Gherardi 2008).
PCTT-M and relativistic computation:
Hogarth 1994
Computing the halting function:
Is
RM
physical?
Németi et al.
Is
RM
physical?
Németi and his colleagues say that the computation is physical in the
sense that “the principles of quantum mechanics are not violated” and
RM
is “not in conflict with presently accepted scientific principles”, and
they suggest that humans might "even build" their relativistic computer
“sometime in the future” (Andréka, Németi and Németi 2009: 501).
•
But see Earman and Norton (1993), Aaronson (2005), Piccinini (2011).
The super-bold (Copeland, Shagrir & Sprevak 2018).
There are, however, questions about the future that do not involve any
specific time but refer to all the future. For example: ‘Is the solar
system
stable?’
,
‘Is the motion of a given system, in a known initial
state,
periodic?’
These are typical questions asked by physicists and
involve (unbounded) quantification over time. Thus, the question of
periodicity is: ‘Does there exist some
T
such that for all times t,
x
i
(T+ t)
= x
i
(t)
for
i =
1, 2, . . . .
n?
Similarly the question concerning stability is:
‘Does there exist some
D
such that for all times
t
the maximal distance
between the particles does not exceed
D?’
(Pitowsky 1996: 163)
The super-bold (Copeland, Shagrir & Sprevak 2018).
•
The motion and stability of physical systems may be simulateable by a
Turing machine, and yet deciding whether the motion (under ideal
conditions) is periodic or will terminate at some point – may be
uncomputable.
•
The situation is similar in the case of the universal Turing machine
itself: the machine's behavior is always Turing computable, yet the
answers to some questions about the behavior, such as whether or
not the machine halts given certain inputs, may not be computable.
The super-bold (Copeland, Shagrir & Sprevak 2018).
•
The super-bold physical Church-Turing thesis (S-
PCTT)
:
Every (“interesting”) physical aspect of the
behavior of any physical system is decidable (Turing
computable).
•
A 2015
Nature
article by Toby Cubitt, David Perez-Garcia, and Michael
Wolf outlined a proof that "the spectral gap problem is algorithmically
undecidable: there cannot exist any algorithm that, given a
description of the local interactions, determines whether the
resultant model is gapped or gapless" (Cubitt et al. 2015: 207).
Summary
•
We distinguished between the original, algorithmic and physicality
variants of CTT.
•
We also distinguished between three theses about physical
computability, the modest the bold and the super-bold theses.
•
Most believe that CTT-O and CTT-A are true.
•
At the present stage of physical enquiry it is unknown whether any of
the physicality theses are true.
•
It can be said that to date there is no empirical evidence against the
physicality theses (so far as we know).
This content delves into the nuances of the Church-Turing Theses, discussing variants like CTT-original and CTT-algorithm. It explores the notions of effectively calculable functions, mechanical and finite procedures, and the sources of finiteness in computation. The discussion also covers what is considered effective, cognitive versus non-cognitive approaches to finiteness constraints, and the definition of an algorithm according to Turing. The content sheds light on the basis for the equivalence of algorithmic procedures and computing machines as proposed by Church's thesis.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
The Church-Turing Theses Oron Shagrir HEPIC seminar, March 2021
The claim: There are different variants of the Church-Turing theses (CTT): CTT-original: refers to what (most of) the founders said CTT-algorithm: refer to what (most) computer science textbooks say. Physicality theses (modest, bold, super-bold): Refer to physical systems. Based on: Copeland and Shagrir, CACM 2019; chapters 2-3 of my The Nature of Physical Computation, OUP (forthcoming).
CTT CTT- -Original (CTT Original (CTT- -O) O) We now define the notion, already discussed, of an effectively calculable function of positive integers by identifying it with the notion of a recursive function of positive integers (or of a -definable function of positive integers) (Church 1936: 100). CTT-O: Every function that can be effectively computed (by an idealized human computer) is Turing computable.
What is effective? G del used the terms mechanical procedure and finite procedure: Mechanical: The outstanding feature of the rules of inference being that they are purely formal, i.e., refer only to the outward structure of the formulas, not to their meaning (G del 1933: 45). Finite: The computation is subject to finiteness constraints, explicated in Turing s analysis of human computers (Turing 1936).
What is the source of finiteness? Cognitive approach: The finiteness constraints reflect the upper limitations on humans cognitive-calculative capacities. Non-cognitive approach: The finiteness constraints reflect the use (epistemic role) of computation in the context of logic and mathematics. (Copeland and Shagrir 2013).
CTT CTT- -Algorithm Algorithm (CTT CTT- -A A) The claim, called Church s thesis or the Church-Turing thesis, is a basis for the equivalence of algorithmic procedures and computing machines (Nagin and Impagliazzo 1995: 611). CTT-A: Any function that can be algorithmically computed by a machine is Turing computable.
What is an algorithm? Turing assumed that a human being can only write one symbol at a time, and this assumption cannot be carried over to a parallel machine that prints an arbitrary number of symbols simultaneously (Gandy 1980: 124 5). In addition to classical sequential algorithms, in use from antiquity, we have now parallel, interactive, distributed, real-time, analog, hybrid, quantum, etc. algorithms. (Gurevich 2012: 32) none of the other known kinds of algorithms seem to threaten the thesis (p. 33).
Physical vs. algorithmic computation Algorithmic computation need not be physical or even physically realizable : Moschovakis and Paschalis say that their approach adopts a very abstract notion of algorithm that takes recursion as a primitive operation and is so wide as to admit non-implementable algorithms (2008: 87). Physical computation need not be finite in the algorithmic sense: It allows infinitely many steps within a terminating computation (supertasks).
The physical Church The physical Church- -Turing Thesis (PCTT) Turing Thesis (PCTT) Wolfram formulated a physical form of the Church-Turing hypothesis : [U]niversal computers are as powerful in their computational capacities as any physically realizable system can be, so that they can simulate any physical system. (Wolfram 1985: 735) Deutsch describes the physical version of the Church-Turing principle : Every finitely realizable physical system can be perfectly simulated by a universal model computing machine operating by finite means (Deutsch 1985: 99).
The physical Church-Turing Thesis (PCTT) [T]he Physical Church-Turing Thesis is the conjecture that whatever physical computing device (in the broader sense) or physical thought-experiment will be designed by any future civilization, it will always be simulateable by a Turing machine. (Andr ka, N meti, and N meti 2009: 500)
The modest and the bold (Piccinini 2011) The Modest Physical Church-Turing Thesis (PCTT-M): Every function computed by a physical system is Turing computable. The Bold Physical Church-Turing Thesis (PCTT-B) Every physical system can be simulated to any specified degree of accuracy by a universal Turing machine. The bold versions proposed in the literature are often "logically independent of one another", and exhibit "lack of confluence" (Piccinini 2011: 747-748)
Pour-El and Richards against PCTT-B Pour-El and Richards (1981) showed that the familiar three- dimensional wave equation produces non-Turing-computable output sequences for some Turing computable input sequences. They also gave an example where the solution to the wave equation maps computable sequences of reals to computable sequences of reals, but the mapping itself is not effectively uniformly continuous. It is controversial whether the requisite input sequences properly encode all the relevant information (Weihrauch and Zhong 2002; Gherardi 2008).
PCTT-M and relativistic computation: Hogarth 1994
Is RM physical? N meti et al.
Is RM physical? N meti and his colleagues say that the computation is physical in the sense that the principles of quantum mechanics are not violated and RMis not in conflict with presently accepted scientific principles , and they suggest that humans might "even build" their relativistic computer sometime in the future (Andr ka, N meti and N meti 2009: 501). But see Earman and Norton (1993), Aaronson (2005), Piccinini (2011).
The super-bold (Copeland, Shagrir & Sprevak 2018). There are, however, questions about the future that do not involve any specific time but refer to all the future. For example: Is the solar system stable? , Is the motion of a given system, in a known initial state, periodic? These are typical questions asked by physicists and involve (unbounded) quantification over time. Thus, the question of periodicity is: Does there exist some T such that for all times t, xi(T+ t) = xi(t) for i = 1, 2, . . . . n? Similarly the question concerning stability is: Does there exist some D such that for all times t the maximal distance between the particles does not exceed D? (Pitowsky 1996: 163)
The super-bold (Copeland, Shagrir & Sprevak 2018). The motion and stability of physical systems may be simulateable by a Turing machine, and yet deciding whether the motion (under ideal conditions) is periodic or will terminate at some point may be uncomputable. The situation is similar in the case of the universal Turing machine itself: the machine's behavior is always Turing computable, yet the answers to some questions about the behavior, such as whether or not the machine halts given certain inputs, may not be computable.
The super-bold (Copeland, Shagrir & Sprevak 2018). The super-bold physical Church-Turing thesis (S- PCTT): Every ( interesting ) physical aspect of the behavior of any physical system is decidable (Turing computable). A 2015 Nature article by Toby Cubitt, David Perez-Garcia, and Michael Wolf outlined a proof that "the spectral gap problem is algorithmically undecidable: there cannot exist any algorithm that, given a description of the local interactions, determines whether the resultant model is gapped or gapless" (Cubitt et al. 2015: 207).
Summary We distinguished between the original, algorithmic and physicality variants of CTT. We also distinguished between three theses about physical computability, the modest the bold and the super-bold theses. Most believe that CTT-O and CTT-A are true. At the present stage of physical enquiry it is unknown whether any of the physicality theses are true. It can be said that to date there is no empirical evidence against the physicality theses (so far as we know).
