Turing machine may be viewed as a computing machine that computes the functions which are defined from integers into integers.

The traditional approach is to represent integers as unary; the integer i ³ 0 is represented by the string 0

^{i}. If a function has k

arguments, i

_{1}, i

_{2},…, i

_{k}, then these integers are initially placed on the tape separated by 1's as .[Different authors

have different approach on the representation of inputs, generally, representation of inputs is not unique].

On the input , if the TM halts with a tape consisting of 0

^{m}for some m, after the computation on this input, then

we say that f(i

_{1},i

_{2}, … , i

_{k}) = m, where f is the function of k arguments computed by this Turing machine.

A function f with integer arguments is said to be

on every input of f.

A function f with integer arguments is said to be

**computable**if there exists a Turing machine M such that M would halton every input of f.

**5.2.1 Example of Computable Functions**

In this subsection we construct or design a Turing machine TM that will compute the "

*proper subtraction function*". That is, we

show that the proper subtraction function is computable. Similarly one can design Turing machine for all the recursive functions.

Thus, it can be proved that all recursive functions are computable functions.

Thus, it can be proved that all recursive functions are computable functions.

**5.2.1.1 Proper Subtraction Function is a Computable Function**

Recall that proper subtraction f(m,n) is defined to be m - n for m > n and zero for m £ n. Now we design a Turing machine,

which will compute proper subtraction for given two integers.

The Turing machine TM, M is defined as follows:

M = ({q

_{0}, q

_{1}, … , q

_{6}}, {0,1},{0,1,B}, d, q

_{0}, B, f), where d is defined below. The TM starts with 0

^{m}10

^{n}on its tape halts

with 0

^{m - n}on its tape. M repeatedly replaces its leading 0 by blank, then searches right for a 1 followed by a 0 and changes the

0 to 1. Next, M moves left until it encounters a blank and then repeats the cycle. The repetition ends if

- Searching right for a 0, M encounters a blank. Then, the n0's in 0
^{m}10^{n}have all been changed to 1’s, and n + 1 of the m 0’s have been changed to B. M replaces the n+1 1’s by a 0 and n B's leaving m - n 0's on its tape.

- Beginning the cycle, M cannot find a 0 to change to a blank, because the first m 0's already have been changed. Then n ³ m, so m n = 0, M replaces all remaining 1’s and 0’s by B.

The transition function d is described below.

- d(q
_{0}, 0) = (q_{1}, B, R)

Begin the cycle, replace the leading 0 by B.

- d(q
_{1}, 0) = (q_{1}, 0, R)

d(q_{1}, 1) = (q_{2}, 1, R)

Searching right, looking for the first 1.

- d(q
_{2}, 1) = (q_{2}, 1, R)

d(q_{2}, 0) = (q_{3}, 1, L)

Searching right past 1’s until encountering a 0. Change that 0 to 1.

- d(q
_{3}, 0) = (q_{3}, 0, L)

d(q_{3}, 1) = (q_{3}, 1, L)

d(q_{3}, B) = (q_{0}, B, R)

Move left to a blank. Enter state q_{0}to repeat the cycle.

- d(q
_{2}, B) = (q_{4}, B, L)

d(q_{4}, 1) = (q_{4}, B, L)

d(q_{4}, 0) = (q_{4}, 0, L)

d(q_{4}, B) = (q_{6}, 0, R)

If in state q_{2}a B is encountered before a 0, we have situation (i) described above. Enter state q_{4}and move left, changing

all 1's to B's until encountering a B. This B is changed back to a 0, state q_{6}is entered, and M halts.

- d(q
_{0}, 1) = (q_{5}, B, R)

d(q_{5}, 0) = (q_{5}, B, R)

d(q_{5}, 1) = (q_{5}, B, R)

d(q_{5}, B) = (q_{6}, B, R)

If in state q_{0}a 1 is encountered instead of a 0, the first block of 0's has been exhausted, as in situation ( ii ) above. M enters

state q_{5}to erase the rest of the tape, then enters q_{6}and halts.

An Illustration of computation of M is a given below:

On the input 0010:

On the input 0100:

An Illustration of computation of M is a given below:

On the input 0010:

On the input 0100:

5.2.2 Computability and Non-computability

*A function or a (decision type) problem is said to be computable, if there exist a Turing machine which computes the function or answer the problem. [i.e., the TM will halt on all the inputs and gives the correct output for all the input]. Otherwise, the function is said to be *

**non-computable.**

Note that there exist Turing Machines to compute the initial functions

- Z (x) = 0, for all x Î N (the zero function)

- S (x) = x+1, for all x Î N (the successor function)

- U
_{i}^{n}(x_{1}, x_{2}, x_{3}, …, x_{i}, ..., x_{n}) = x_{i }(the projection function)

There also exist Turing machines to compute composition, recursion and minimization operations.

**As every partial function is**

obtained from the initial functions by a finite number of applications of the operations of composition, recursion and minimization, thus, there exist Turing machine that can compute every partial recursive function. Thus, every partial recursive function is computable. On the other hand it can be proved that every Turing computable function is partial recursive.

obtained from the initial functions by a finite number of applications of the operations of composition, recursion and minimization, thus, there exist Turing machine that can compute every partial recursive function. Thus, every partial recursive function is computable. On the other hand it can be proved that every Turing computable function is partial recursive.

Here we give

**some examples of non-computable problems.**

"Halting problem" for Turing machine is one of the popular examples for non-computability of Turing machines. This is the problem

of finding a decision procedure which would enable one to determine in a finite number of steps, given any Turing machine T and

premarked tape 't', whether or not the machine will ever make d(s

^{j}, a

^{j}) = HALT. Equivalently the problem is to construct a Turing

machine, which will accept just those pairs (T, t) that will come to HALT, and reject just those pairs (T, t) that will not come to

HALT. It can be proved theoretically that there cannot exist any Turing machine, which will perform this job. Thus, the

"HALTING PROBLEM IS NONCOMPUTABLE".

"HALTING PROBLEM IS NONCOMPUTABLE".

Other interesting example of noncomputable functions are the following.

For any programming language, to determine whether or not

(a) a given program that can loop for ever on some input,

(b) a given program that can ever produce an output on given input,

(c) a given program that eventually halts on the given input.

Note to the Reader

Note to the Reader

To understand and appreciate the depth of the concepts of computability and non-computability, one has to have good

understanding in formal languages and theory of computing, so readers are advised to refer good books for detailed study on

these topics [some of the books are given in the

**Reference**]. Here we have introduced this topic mainly because; "all partial

recursive functions are computable. Also understanding about the Turing machine will help to study other important Theoretical

Computer Sciences topics like Computation and Complexity etc.

## No comments:

Post a Comment