Church-Turing Thesis :
There is no algorithm that, given a program of P and an input of that program, can determine whether or not the given program will eventually halt on the given input.
Halt(x,y) Predicate can be proven by Proof by Contradiction. x is an input and y is the program number. At the end we come the a contradiction as follows :
Halt(y,y) = ~Halt(y,y) Which is contradiction.
Minimalization is the maximum value smaller than a value that satisfies the function.
i.e: We want to find the maximum square of a number that s smaller than, 33.
We try 1,2,3,4,5 and their square is smaller than 33, then we try 6 whose square is 36 which is larger than 33 hence we pick five as the largest minimum number whose square is less than 33.
This is bounded minimalization.
There is also maximization, minimum value smaller than a value that satisfies the function.
Iterated Operations are about iteration of functions.
for n=0 to 1 f(n) = g(n)
g(n) = f(1)+f(2)+f(3)+…….+f(n)
We know that addition is primitive recursive so g(n) is primitive recursive. Thus, we can say that g(n) belongs to a PRC class if f(n) belongs to a PRC class.
Moreover,
g(n) = f(1)*f(2)*f(3) ….. *f(n)
We saw that multiplication is primitive recursive, if f(n) is primitive recursive so is g(n). If f(n) belongs to a PRC class so is g(n).
In terms of Predicates, addition of P(n) shouldn’t be equal to 0 (zero), then g(n) is primitive recursive predicate for addition.
Also, P(n) multiplication from n to 1 should be equal to 1, then g(n) is primitive recursive predicate.
Predicates or Boolean valued functions are simply total functions whose values are either 0 or 1 (True or False).
1 – x = y
This is a primitive recursive predicate, given x and y, are they equal or not. yes or no answer. if they are equal P(x,y) is 1 otherwise 0.
2- x<= y
3- x<y
All these predicates can be written by other primitive recursive functions and initial functions, hence they are Primitive Recursive Predicates. If P and Q are a primitive recursive predicates so it ~P (Not P), P || Q and P && Q.
Reminder : We defined initial functions namely, null function, successor function and projection function, we defined composition and recursion. A function is primitive recursive if it can be obtained from initial functions by finite number of applications of composition and recursion. We defined a class of total functions L is called a PRC class if it the initial functions belong to L and a function in L can be obtained by functions in L by composition and/or recursion. A class of computable functions is PRC class. A function is primitive recursive if and only if it belongs to every PRC class. Primitive recursive functions are computable, which means they are total and we can write a program for it. PRC Class.
Here are some primitive recursive functions:
1 – x+y
2 – x.y
3- x!
4 – p(x) , predecessor of x as , x-1
5 – |x-y| , distance of x and y.
6 – alpha(x) = 1 ,if x =0
alpha(x) = 0, if x!= 0
7- x to the power of y
8- x-y = x-y if x>y else 0
There are many other primitive recursive functions, that will be covered in other posts.
PRC stands for Primitive Recursively Closed. There are PRC classes that will be discussed in this.
First we need to define some initial functions, namely null function, successor function and projection function.
Null function:
n(x) = 0
Successor function:
s(x) = x+1
Projection function :
P(n,i, x1,x2,x3….,xi,..,xn) = xi , 1<= i <= n
Given a number i greater or equal to 1 and less than or equal to n , projection function outputs the value of i th output.
Definition : A class of total functions L is called PRC class if :
Theorem : A class of computable functions is a PRC class.
We have showed that composition and recursion is computable and initial functions are computable. Therefore Class of computable functions are PRC class.
Definition : A function is primitive recursive if it can be obtained from initial functions by finite number of applications of composition and recursion.
Corollary: The class of Primitive Recursive functions is a PRC class.
Theorem : A function is Primitive Recursive if and only if it belongs to every PRC class.
Corollary : Every Primitive Recursive function is computable.
These are the most fundamental and important definition Theory of Computation.
Reminder: A Partially computable function is a function that we can write a program for it using increment, decrement and conditional branch. Computable functions are Partially Computable and total functions. Computable functions are total functions that we can write a program for.
Theorem :
h(0) = n,
h(t+1) = g( t, h(t))
Let g be a total function then h is said to be obtained from g by recursion.
How does this work :
h(t+1) = g(t, h(t))
h(t) = g(t-1, h(t-1))
h(t-1) = g( t-2 , h(t-2))
.
.
.
h(0) = n
This is how h is obtained from g by recursion.
If g is computable so is h. We said g is a total function, it s computable, so it h is computable, hence total.
Recursion is one of the most important concept in computer science.
Reminder: A Partially computable function is a function that we can write a program for it using increment, decrement and conditional branch. Computable functions are Partially Computable and total functions. Computable functions are total functions that we can write a program for.
We want to combine computable functions so that output of one becomes input of another one .
F(x) = H(G(x))
This is called composition. For every input for x, H(G(x)) produces a result for F function, because it s total and we can write such a program as following:
Z<- G(X)
Y<- H(Z)
This program computes the function above and F s said to be obtained from other functions by composition. i.e: Combining function with each other to generate other functions is called Composition.
Remark: If F is obtained from (partially) computable functions by composition then F is (partially) computable. This means both side can be partially computable or computable. In other words the equation shouldn’t necessarily be total.
Primitive Recursive functions are closed under Composition. This is a very important theorem about composition.
A Programming Language :
X<-X+1
X<-X-1
if X != 0 GOTO Label
We will be using these 3 operations, namely increment, decrement and conditional brach operators to define programs.
We will have Labels as A1 , B1, C1,… E…
E is a label that program halts. Basically Exits.
We have input and output variables as follows : X1,X2,X3…., Y and Z1,Z2,Z3….
Y variable holds the output of the programs while X variable(s) hold the input(s) of the program and Z variables are local variable that can be used within a function, program. The default values of these variables are zero. If these variables are not initialized with a value, they hold 0.
Example 1.1 :
[A] X<- X-1
Y<- Y+1
IF X != 0 GOTO A
This program as obvious, inputs X and outputs Y which takes the value of X. While decrementing the value of X by 1, increment the value of Y by 1. which makes a copy of X into Y and outputs Y at the end of the program. As you can see [A] is a Label and IF statement goes to that label while X is not equal to 0.
Here is another example Y = 2X , 1.2:
Z<- X
[A]Â X <- X-1
Y<-Y+1
IF X != 0 GOTO A
[B]Â Z<-Z-1
Y<-Y+1
IFÂ Z != 0 GOTO B
This program computes Y + 2X , Z is a local variable, You might say Z<-X is not a valid operation but it s a macro as we defined in Example 1.1, we can reuse the macros.
We can computer every single Mathematical calculation using this programming language. It might be very messy and time consuming however it s possible.
An instruction is either a statement or a Label followed by a statement.
Ex 1.3:
X <- X-1
[A]Â X<-X+1
A program is a list of statements.
The length of the program is the number of the statement(s) that the program contains. Program can contain zero length statements, which constructs Empty program.
A State of the program P, is the list of Equations as X1 = n, Z3= i …. while execution the program. In short A state of the program is while executing a statement, value of the variables. A variable can not hold more than one value. There can be two variable with the same name. A program has an initial state and final state.
So far we defined the line numbers of the program that points to the statement, and we defined the state of the program, in order for a program to execute it should know it s state and the line number (Which line to execute next). This is called a snapshot or instantaneous description of the program. i.e: Which statement is the program executing and what are the values of the variables so far. There is initial snapshot of the program and there is terminal snapshot of the program. Successor of the terminal snapshot is the end of the program.
A partial function F is said to be partially computable if it can be computed by a program. That s F is partially computable if we can write a program for it.
Remark : From set theory we know that a function is total for every input in its domain there is an output in its range. A function is a partial function if there is an output for a subset of input in it s domain. Partial Functions are subset of Total functions.
Again, Partially computable functions are functions that we can write a program for it.
Computable function is a partially computable function which is also total.
Partially Computable functions are called Partially Recursive functions and Computable functions are called recursive functions.
Written by
Recent Comments