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 0i. If a function has k
arguments, i1, i2,…, ik, 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 0m for some m, after the computation on this input, then
we say that f(i1,i2, … , ik) = m, where f is the function of k arguments computed by this Turing machine.
A function f with integer arguments is said to be computable if there exists a Turing machine M such that M would halt
on 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.
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 = ({q0, q1, … , q6}, {0,1},{0,1,B}, d, q0, B, f), where d is defined below. The TM starts with 0m10n on its tape halts
with 0m - 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 0m10n 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(q0, 0) = (q1, B, R)
Begin the cycle, replace the leading 0 by B.
- d(q1, 0) = (q1, 0, R)
d(q1, 1) = (q2, 1, R)
Searching right, looking for the first 1.
- d(q2, 1) = (q2, 1, R)
d(q2, 0) = (q3, 1, L)
Searching right past 1’s until encountering a 0. Change that 0 to 1.
- d(q3, 0) = (q3, 0, L)
d(q3, 1) = (q3, 1, L)
d(q3, B) = (q0, B, R)
Move left to a blank. Enter state q0 to repeat the cycle.
- d(q2, B) = (q4, B, L)
d(q4, 1) = (q4, B, L)
d(q4, 0) = (q4, 0, L)
d(q4, B) = (q6, 0, R)
If in state q2 a B is encountered before a 0, we have situation (i) described above. Enter state q4 and move left, changing
all 1's to B's until encountering a B. This B is changed back to a 0, state q6 is entered, and M halts.
- d(q0, 1) = (q5, B, R)
d(q5, 0) = (q5, B, R)
d(q5, 1) = (q5, B, R)
d(q5, B) = (q6, B, R)
If in state q0 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 q5 to erase the rest of the tape, then enters q6 and halts.
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
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)
- Uin(x1, x2, x3, …, xi, ..., xn) = xi (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.
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(sj, aj) = 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".
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
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