Transcript Turing Machines - University of Alberta

CMPUT 272
Formal Systems
Logic in CS
I. E. Leonard
University of Alberta
http://www.cs.ualberta.ca/~isaac/cmput272/f03
Nov 4, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
1
All illustrations are copyright to their respective copyright holders and are reproduced here under the conditions of fair use
Today
Sets (finishing off)
Paradoxes (at a very basic
level)
QuickTime™ and a TIFF (Uncompressed) decompressor are needed to see this picture.
Turing machines
Halting problem
Nov 4, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
2
Cartesian Products
Intuition first:
Suppose I have a function that takes
two numbers x and y and returns x/y
What is the set of valid inputs?
Is it just R?
No -- cannot divide by 0
Is it R\{0}?
No -- can happily have 0 as x
Nov 4, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
3
Combinations
Suppose I have:
two independent attributes: sky conditions
and temperature
two values for the sky conditions
S={sunny, overcast};
three values for the precipitation:
P={snow, rain, nothing}.
How many combinations can I have?
Nov 4, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
4
Combinations - 2
6 combinations:
<sunny, rain>
<sunny, snow>
<sunny, nothing>
<overcast, rain>
<overcast, snow>
<overcast, nothing>
So the set of these 6 pairs is somehow a
result of the original sets S and P
What is this operation?
Nov 4, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
5
Cartesian Product
Set C is a Cartesian Product of set
A and set B iff it is a set of all
ordered pairs such that the 1st
element belongs to A and the 2nd
element belongs to B
ABC [C=A  B 
ab (<a,b>C  (aA & bB))]
Nov 4, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
6
Examples
A={0,1}, B={Angela,Belinda}
AB = {<0,Angela>, <0,Belinda>, <1,Angela>,
<1, Belinda>}
A={0,1}, B={Angela,Belinda}
BA = {<Angela,0>, <Belinda,0>, <Angela,1>,
<Belinda,1>}
A={0}, B={a,b}, C={1,2}
ABC={<0,a,1>,<0,b,1>, <0,a,2>,<0,b,2>}
Nov 4, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
7
More examples
A=B=C=D=R (set of all real numbers)
ABCD=R4 (time-space continuum)
What is the cardinality of Cartesian Product?
|A1  …  An|=|A1| · … · |An| for finite sets
How about {}  {1,2}?
{}  {1,2}={}
Nov 4, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
8
Questions
Nov 4, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
9
Formal Languages
Used to formalize computability, etc.
Alphabet: any finite set of symbols
A string from an alphabet is an n-tuple of
symbols from the alphabet (n is a natural
number, possibly 0)
A formal language over an alphabet is any set
of strings from the alphabet
Some effective rule for determining if a string
is in the language is usually assumed to exist
Nov 4, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
10
More Notation
∑n = {s | s is a string from ∑, |s|=n}
Clearly: ∑n = ∑  …  ∑ (n times)
∑* = {s | s is a string from ∑}
Note that all strings are finite
Clearly: ∑* = ∑0  ∑1  …
Examples
Nov 4, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
11
Properties of Ø
Empty set has 0 elements
Empty set is a subset of any set
Empty set is unique
Union with the empty set gives the
same set back
Intersection with the empty set gives
empty set
Complement of the empty set is the
universal set
Nov 4, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
12
Power Set
Power set of set A, denoted by P(A) or
2A, is the set of all subsets of A
What set is guaranteed to be an
element of any P(A)?
The empty set
Examples
Cardinality (size) of power set (theorem
5.3.6):
If |A|=n then |P(A)|=2n
Nov 4, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
13
Proofs
Proof #1 : using mathematical induction
Proof #2 : using number of bit strings
of length n
Nov 4, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
14
Questions
Nov 4, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
15
Paradoxes
What is a paradox?
par·a·dox
Pronunciation: 'par-&-"däks
Function: noun
Etymology: Latin paradoxum, from Greek paradoxon, from
neuter of paradoxos contrary to expectation
1:a tenet contrary to received opinion
2a :a statement that is seemingly contradictory or opposed
to common sense and yet is perhaps true
2b:a self-contradictory statement that at first seems true
2c:an argument that apparently derives self-contradictory
conclusions by valid deduction from acceptable premises
3:one that possesses seemingly contradictory qualities or
phases
Nov 4, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
16
Liar’s Paradox
Have encountered when considering
Knaves & Knights
Any recollections?
Knaves always lie
Knights always say truth
What if one of the inhabitants of the
island says:
“I am a Knave”
What is she?
Nov 4, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
17
Alternative Versions
“I’m lying”
“This sentence is false”
Nov 4, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
18
Problems
So the problem is that we cannot assign
truth value to such statements
They are neither true nor false
Nov 4, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
19
Barber’s Paradox
Suppose there lives a barber that shaves all
men who do NOT shave themselves and only
them
Does the barber shave himself?
Suppose ‘yes’. Then he would be one of the men
he shaves and, therefore, one of the men who do
not shave themselves. Then he cannot shave
himself.
Suppose ‘not’. Then he is one of the men who
don’t shave themselves and therefore must be
shaven by the barber. Thus, he must shave
himself.
Nov 4, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
20
Russell’s Paradox
Many sets are not elements of
themselves:
Example: {2}{2}
Some sets are elements of themselves
Example: a set of all concepts
Suppose set S is the set of all sets that
are NOT elements of themselves
Is S an element of itself?
Nov 4, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
21
Reasoning
Suppose SS. Then S must be one of
the sets that are not elements of
themselves (by definition of S).
Therefore, SS. Contradiction.
Suppose SS. Then S must be one of
the sets that are indeed elements of
themselves. Thus, SS. Contradiction.
Nov 4, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
22
A workaround
The problem seems to lie with
the fact that we can express
anything we like using the
predicative form of sets:
A={x | P(x)}
QuickTime™ and a TIFF (Uncompressed) decompressor are needed to see this picture.
Too powerful?
Possible restriction:
Whenever defining a set, require
that there exists an enveloping set
such that: A={xB | P(x)}
Nov 4, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
23
Why does it help
So now Russell’s set S is defined as:
The set of all sets that are elements of B and are
NOT elements of themselves.
Suppose S is an element of itself. Then S is
not an element of itself by definition of S.
Contradiction.
Suppose S is not an element of itself. Then it
simply means that S is not an element of B.
No contradiction.
Nov 4, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
24
Questions
Nov 4, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
25
Barber Paradox
Can we use a similar trick to “resolve”
the Barber’s paradox?
More later …
Nov 4, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
26
Refresher : Logic
In logic, what are the following
concepts?
Sentences
Derivations
Axioms
Consistency of an axiom system
Completeness of an axiom system
Nov 4, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
27
Gödel’s Incompleteness
A deep topic : mathematically and
philosophically
Cartoon version:
"Wir mussen wissen; wir werden
wissen.” ("We must know; we shall
know.”) -- David Hilbert's life’s belief
In 1931 Kurt Gödel showed that
there are logical statements that are
consistent but cannot be proved or
disproved
This news affected Hilbert deeply
Nov 4, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
QuickTime™ and a TI FF (Uncompressed) decompressor are needed to see this pict ure.
Qu ic kTi me™ a nd a TIFF (U nc omp res se d) de co mpre ss or are n ee de d to se e thi s p i cture .
28
Another Angle
Hilbert had struggled to find a logical
foundation of the entire mathematics that
would be consistent
any finite sequence of derivations would NOT lead
to a contradiction
Gödel showed that any consistent
axiomatization powerful enough to express
arithmetic is necessarily incomplete
There exist statements that are consistent with
the axioms but cannot be proven or disproved
Therefore, Hilbert’s goal is not realizable
Nov 4, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
29
A Taste Of Incompleteness
Consider the following statement:
“This sentence cannot be derived from a given system of
axioms”
Suppose it is expressible in the system of axioms
Is it consistent with the system?
Suppose it is inconsistent (“false”). Then it can be proven in
the given system of axioms. If the system is consistent in
itself then the statement must be true. But then it cannot be
derived. Contradiction.
Suppose it is consistent (“true”). Then it cannot be derived.
No contradiction.
Bottom line: for any consistent and sufficiently
powerful axiomatization there exist unprovable but
consistent (“true”) statements.
Nov 4, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
30
Questions
Nov 4, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
31
What about CS?
Applications to CS?
Of course!
Here is one (in a nutshell):
There exist NO algorithm that can look at
any algorithm A and tell if A will halt on
input x
This is called the Halting Problem and
was investigated by the founder of
Artificial Intelligence, Alan M. Turing
Nov 4, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
32
Wait a minute…
How can one possibly know if no
algorithm exists for a task?
People’s creativity appears unbounded!
Are there really limits to what we can
compute?
If someone can define a task in a
reasonable fashion on paper there must
be a way to write a program for it,
right?
What is an algorithm anyway?
Nov 4, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
33
Formalization of Computability
In order to take such discussions beyond
hand-waiving, Turing suggested a simple
computational device (LCM now known as the
Turing Machine)
The punch line is : it is believed that anything
computable can be programmed on a Turing
Machine
Hence the formal definition of what
computable things are
Nov 4, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
34
Turing Machines
So what is a Turing machine then?
Nov 4, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
35
Notes
All Turing machines (TM) can be enumerated:
TM0, TM1, TM2, …
For every computable function there is a
Turing machine that realizes that function and
vice versa
TMs are a simple but supremely rich
computational formalism
No one actually programs in TM language
directly (too cumbersome)
Any computational language/platform can be
expressed in TM
Nov 4, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
36