Great Theoretical Ideas In Computer Science Steven Rudich Lecture 3 CS 15 251 Jan 20 2004 Spring 2004 Carnegie Mellon University Unary Binary and Beyond 1 X X X X 1 2 3 n 2 n X n 1 1 X X1 We are going to need this fundamental sum The Geometric Series A Frequently Arising Calculation X 1 1 X1 X2 X 3 Xn 2 Xn 1 X1 X 2 X 3 Xn 1 Xn 1 X1 X2 X 3 Xn 2 Xn 1 1 Xn 1 Xn The Geometric Series X 1 1 X1 X2 X 3 Xn 1 Xn 1 n X 1 2 3 n 2 n 1 1 1 X X X X X X1 when X 1 Last time we talked about unary notation nth Triangular Number n 1 2 3 n 1 n n n 1 2 nth Square Number n 1 3 2n 1 Sum of first n odd numbers nth Square Number n n n 1 n2 n 2 n 1 2 n n 2 n We will define sequences of symbols that give us a unary representation of the Natural number First we define the general language we use to talk about strings Strings Of Symbols We take the idea of symbol and sequence of symbols as primitive Let be any fixed finite set of symbols is called an alphabet or a set of symbols Examples 0 1 2 3 4 a b c d z all typewriter symbols Strings over the alphabet A string is a sequence of symbols from Let s and t be strings Let st denote the concatenation of s and t i e the string obtained by the string s followed by the string t Define by the following inductive rules x2 x2 s t 2 st 2 Intuitively is the set of all finite strings that we can make using at least one letters from Define be the empty string I e X Y XY for all strings X and Y is also called the string of length 0 Define 0 Define Intuitively is the set of all finite strings that we can make using letters from including the empty string The Natural Numbers 0 1 2 3 Notice that we include 0 as a Natural number God Made The Natural Numbers Everything Else Is The Work Of Man Kronecker 0 1 2 3 Last Time Unary Notation 1 2 3 4 To handle the notation for zero we introduce a small variation on unary Peano Unary PU 0 1 2 3 4 5 6 0 S0 SS0 SSS0 SSSS0 SSSSS0 SSSSSS0 Giuseppe Peano 1889 Each number is a sequence of symbols in S 0 0 1 2 3 4 5 6 0 S0 SS0 SSS0 SSSS0 SSSSS0 SSSSSS0 Peano Unary Representation of Natural Number 0 S0 SS0 SSS0 0 is a natural number called zero Set notation 0 2 If X is a natural number then SX is a natural number called successor of X Set notation X 2 SX 2 Inductive Definition of 0 S0 SS0 SSS0 Inductive definition of addition X Y 2 X 0 X X SY S X Y S0 S0 SS0 i e 1 1 2 Proof S0 S0 S S0 0 S S0 SS0 X Y 2 X 0 X X SY Inductive Definition of 0 S0 SS0 SSS0 Inductive definition of times X Y 2 X 0 0 X SY X Y X Inductive Definition of 0 S0 SS0 SSS0 Inductive definition of raised to the X Y 2 X 0 1 X SY X Y X or X0 1 or XSY XY X 0 S0 SS0 SSS0 Defining for 8 x y 2 x y is TRUE y x is FALSE x y is TRUE y x is FALSE x 1 0 is TRUE x 1 y 1 is TRUE x y is TRUE 0 1 2 3 Defining partial minus for 8 x y 2 x 0 x x y x 1 y 1 x y a a DIV b b a MOD b Defining DIV and MOD for The maximum number of times b goes into a without going over 8 a b 2 a b a DIV b 0 a b 0 a DIV b 1 a b DIV b a MOD b a b a DIV b The remainder when a is divided by b 45 45 DIV 10 10 45 MOD 10 4 10 5 Defining DIV and MOD for 8 a b 2 a b a DIV b 0 a b 0 a DIV b 1 a b DIV b a MOD b a b a DIV b We have defined the Peano representation of the Naturals with a notion of DIV and MOD PU takes size n 1 to represent the number n Higher bases are much more compact 1000000 in Peano Unary takes one million one symbols to write 1000000 only takes 7 symbols to write in base 10 Let s define base 10 representation of PU numbers Let 0 1 2 3 4 5 6 7 8 9 be our symbol alphabet Any string in will be called a decimal number Let X be a decimal number Let s define the length of X inductively length 0 X aY a2 Y2 length X S length Y Let X be decimal Let n unary length X For each unary i n we want to be able to talk about the ith symbol of X The ith symbol of X Defining rule X PaS where P S2 and a2 i length S a is the ith symbol of X For any string X we can define its length n2 PU For all i2 PU s t i n we can define the ith symbol ai X an 1 an 2 a0 We define a base conversion function Base10 to 1 X to convert any decimal X to its unary representation Initial Cases length X 1 Base10 to 1 0 0 Base10 to 1 1 S0 Base10 to 1 2 SS0 Base10 to 1 3 SSS0 Base10 to 1 9 SSSSSSSSS0 Suppose n length X S0 For all i n let ai be the ith symbol of X Hence X an 1 an 2 a0 Define Base10 to 1 X i n Base10 to 1 ai 10i where and are defined over PU Example X 238 Base10 to 1 238 2 100 3 10 8 Base10 to 1 an 1 an 2 a0 an 1 10n 1 an 2 10n 2 a0 100 Now we want to go back the other way We want to convert PU to decimal No Leading Zero Let NLZ be the set of decimal numbers with no leading 0 leftmost symbol 0 or the decimal number 0 We define Base1 to 10 from PU to NLZ It will turn out to be the inverse function to Base10 to 1 One digit cases Base1 to 10 0 0 Base1 to 10 S0 1 Base1 to 10 SSo 2 Base1 to 10 SSSSSSSSS0 9 Suppose X 9 Let n be the smallest unary number such that 10n X 10n 1 X Let d X DIV 10n …
View Full Document
Unlocking...