Computable Function

Sets

Functions

Relations & predicates

Logical notation

Algorithms, effective procedures

Unlimited Register machine

Decidable predicates

Khaled A.

Mina S.

Done By:-

**Computability**

Titles:-

Sets

Functions

Relations & predicates

logical notation

Algorithms, effective procedures

The URM

URM - computable fuctions

Decidable predicates and problems

Computability on other domains

A

x

x

A

x is member of set A

A

B

A is subset of B

x

A

B

x is intersected between A and B.

A

B = x

x

A & B

A

B

x

x

x

A

OR

x

B

OR

Both A & B

A\B

A-B

The difference between A and B

OR

the relative complement

A's complement

What is the Function?

Dom(A) and Ran(B)

Domain: {1, 2, 3, 4}

Codomain: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

Range: {3, 5, 7, 9}

Predicates

if

2<3 is true (holds)

5>9 is false (doesn't hold)

Equivalence order

When?

Example on x,y,z A

Reflexivity

R(x,x);

Symmetry

if R(x,y) then R(y,x);

Transitivity

if R(x,y)&R(y,z)thenR(x,z);

Partial order

When?

Ir-reflexivity

not R(x,x);

Transitivity

if R(x,y)&R(y,z) then R(x,z);

Example on x,y,z A

Algorithms

mechanical rule or automatic method or program for performing some mathematical operations

What is it?

Algorithms Types

given n , finding the nth prime number.

differentiating a polynomial.

finding the highest common factor.

if x is multiple of y. [mod]

What Algorithms look like!

URM

What is it?

Abstraction or idealization of computing device

It's characteristics:-

Register

program

instructions

operations

termination

Registers

A URM has a number of locations called Registers which can store nutral numbers {0,1,2,3....}

URM Programs use finite number of registers

Registers are refereed BY R ex: R1 ,R2 ...

the number held bu registers is reffered by r ex: r1 ,r2 ,r3 ...

The Registers are unlimited in the following two Senses:

Although URM uses finit number of Registers, there is no actual bound on how many a program can actually use.

There is no actual bound on the size of the natural numbers that maybe stored in a Register

Program

Finite list of instructions

Instructions are writen in a fixed order

For historical reasons the number of instructions is called line numbers.

Basic Instructions :)

PS: At the End of teh Running the result is found in register R1

Lets Solve an Example

any questions!

Example on Basic Instructions

Example :-

If x is multiple of y

ex: if 18 is multiple of 2 --->1 OR yes

Decidable Predicate

When?

If

function is computable

then it may be decidable or not

BUT

If

function is not computable

then it is not decidable

Ref:

Theory of Computation"St. Joseph’s College of Engineering & Technology Palai"

Elisa Elshamy:How To Think About Algorithms

Nigel Cutland: Computability

John C. Shepherdson, Howard E. Sturgis: Computability of Recursive Functions.

A.I. Mal'tsev:Algorithms and recursive functions

Rockafellar, R. T. : Convex Analysis