5 COMPUTABLE FUNCTIONS
Computable functions are de?ned on the set of nonnegative integers. Some texts use N to denote this set. We use N to denote the set of positive integers, so we will use the notation
N0 = {0, 1, 2, 3,.. .}
Throughout this section, the terms number, integer, and nonnegative integer are used synonymously. The preceding section described the way a Turing machine M manipulates and recognizes character data. Here we show how M manipulates numerical data. First, however, we need to be able to represent our numbers by our tape set A. We will write 1 for the tape symbol a1 and 1n for 111 ... 1, where 1 occurs n times.
De?nition 12: Each number n will be represented by the tape expression )n* where )n*= 1n+1 . Thus:
)4*= 11111 = 15 , )0*= 1, )2*= 111 = 13 .
De?nition 13: Let E be an expression. Then [E] will denote the number of times 1 occurs in E. Thus
[11Bs2 a3 111Ba4 ]= 5, [a4 s2 Ba2 ]= 0, [)n*] = n + 1.
De?nition 14: A function f : N0 ? N0 is computable if there exists a Turing machine M such that, for every integer n, M halts on )n* and
f (n) = [term(?()n*)]
We then say that M computes f .
That is, given a function f and an integer n, we input )n* and apply M . If M always halts on )n* and the
number of 1’s in the ?nal picture is equal to f (n), then f is a computable function and we say that M computes f .
EXAMPLE 4 The function f (n) = n + 3 is computable. The input is W = 1n+1 . Thus we need only add two 1’s to the input. A Turing machine M which computes f follows:
M = {q1 , q2 , q3 }= {s0 1s0 L, s0 B 1s1 L, s1 B 1sH L}
Observe that:
(1) q1 moves the machine M to the left.
(2) q2 writes 1 in the blank square B , and moves M to the left. (3) q3 writes 1 in the blank square B , and halts M .
Accordingly, for any positive integer n,
s0 1n+1 ? s0 B 1n+1 ? s1 B 1n+2 ? sH B 1n+3
Thus M computes f (n) = n + 3. It is clear that, for any positive integer k, the function f (n) = n + k is computable.
The following theorem applies.
Theorem 4: Suppose f : N0 ? N0 and g : N0 ? N0 are computable. Then the composition function
h = g ? f is computable.
We indicate the proof of this theorem here. Suppose Mf and Mg are the Turing machines which compute
f and g, respectively. Given the input )n*, we apply Mf to )n* to ?nally obtain an expression E with [E]= f (n).
We then arrange that E = s0 1f (n) . We next add 1 to E to obtain E = s0 11f (n) and apply Mg to E . This yields
E where [E ]= g(f (n)) = (g ? f )(n), as required.
Functions of Several Variables
This subsection de?nes a computable function f (n1 , n2 ,..., nk ) of k variables. First we need to represent the list m = (n1 , n2 ,..., nk ) in our alphabet A.
De?nition 15: Each list m = (n1 , n2 ,..., nk ) of k integers is represented by the tape expression
)m*= )n1 *B )n2 *B ··· B )nk *
For example, )(2, 0, 4)*= 111B 1B 11111 = 13 B 11 B 15 .
المادة المعروضة اعلاه هي مدخل الى المحاضرة المرفوعة بواسطة استاذ(ة) المادة . وقد تبدو لك غير متكاملة . حيث يضع استاذ المادة في بعض الاحيان فقط الجزء الاول من المحاضرة من اجل الاطلاع على ما ستقوم بتحميله لاحقا . في نظام التعليم الالكتروني نوفر هذه الخدمة لكي نبقيك على اطلاع حول محتوى الملف الذي ستقوم بتحميله .