### Present Remotely

Send the link below via email or IM

• Invited audience members will follow you as you navigate and present
• People invited to a presentation do not need a Prezi account
• This link expires 10 minutes after you close the presentation

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

# Computability

No description
by

## Mino Basha

on 24 November 2014

Report abuse

#### Transcript of Computability

Chapter 1
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
Full transcript