# Introduction to Theoretical Computer Science (Series in Computer Science, Volume 23)

## Xiwen Ma

Language: English

Pages: 121

ISBN: 9810201931

Format: PDF / Kindle (mobi) / ePub

The contents of this book are self-sufficient in the sense that no preliminary knowledge other than elementary set theory is needed and there are no complicated mathematical theorems in the book.

A must for those entering the field.

Cyberpatterns: Unifying Design Patterns with Security and Attack Patterns

GPU Pro 7: Advanced Rendering Techniques

Concise Computer Vision: An Introduction into Theory and Algorithms (Undergraduate Topics in Computer Science)

Data Mining and Knowledge Discovery Handbook (Springer series in solid-state sciences)

Operating Systems: Internals and Design Principles (6th Edition)

Probabilistics Search for Tracking Targets: Theory and Modern Applications

x)=Fs:x for all s, x £ Dn. U is the universal function of C. If / is a computable function, then there exists an S-expression s such that f = F,. We say that s is a program of / . 2. 4. 4. Example. The empty function _L is computable. To see this, let s be the program of a. Then \$' = const iQ is the program of 0, and s"= comp(s, s1) is the program of a ° 0 = J=. 47 2. 4 Abstract S-expression Computer 2. 4. 5. Example. The function v=I^*Q | 1 is computable. To see this, let « be the program of

the three expressions denoted by pi, p2 and pa, in that order, with the condition operator. (where ID, CAR, CDR, ATOM, EQ, EMP, CONST, CONS, COMP and COND are different atoms in D and none of them is 0). In other words, the set F of F-expressions is the formal solution of the following set equation: X S B + {CONST) X Dn + {CONS, COMP) X X2 + {COND) X X3 where B= {ID,CAR,CDR,ATOM,EQ,EMP). Thus F is a subset of Du and each F-expression is an S-expression. Using this notation, we can say that the

Fortunately, it can be proved from other axioms. (4) An unary function such that Q(x) # x, for all x £ D is called a distinction function. For example Q ( x ) = r + 1 is a distinction function for natual numbers. There are many distinction functions. It is our intuition that at least one of them is computable. (5) The selection function is a 4-ary function such that . Is if x = y A(x,y,s,t) = I \t if x 96 y Now we are to state the corresponding axioms, but some preliminary explanations are

computable and pn is its program. 1. 2. 2. Example. (Diagonal function). We obtain in example 1. 1. 5 that: 6= U™ ° . By axiom (B) , 6 is computable and the corresponding program is hn(.Ui,pn , Pn)1. 2. 3. Problem. Let / and g are 3-ary functions such that f(x,y,z) = g(y,z,x). If / is computable and i is its program, show that g is computable by finding its program. Let / = F,(2) be a 2-ary computable function and d £ D. The function g = / o {dm ,1) is an unary function such that

numbers is based on the following: (0) a given natural number 0; (s) a successor function s, s(x) is the successor of x. The basic property of them are: (1) Every number has a successor, and every number other than 0 is a successor of some number, while 0 is not a successor of any num­ ber. (2) Distinct numbers have distinct succesors. 21 2. 1 Recursive Domains (3) The set of natural numbers are exactly the set: {0, s ( 0 ) , s ( s ( 0 ) ) , -}• In mathematics. N is usually defined