Related to discrete mathetics. - Prove that the busy bever function defined as f
ID: 3110569 • Letter: R
Question
Related to discrete mathetics.
- Prove that the busy bever function defined as follows is not computable:
for every positive integer n, the busy bever function Sigma(n) is the
greatest value that can be stored in the variable X1 by using any halting
program of length exactly n, starting from X1 = 0, where X1 is an identifier
used in a program written in the programming language defined on this photo.
please give a clear explanation writtin by keyboard.
you can get the information from thios photo.
The Busy Beaver Problem Pro- putable by another ers: Xi, X2, X3 gramming Version Applying Lemma 2 to b (n), for every n (n+k)2b(n) Assignment statements The len gth n of a program Pis its number of lines, counting every (2n). Considering n k+1, we obtain (k+1+k) (2 (k+1)) hence assignment, "do" and "od" as a Xi: Xj 1 (operating in 302k+1)202k+2), but by apply. ne. The busy-beaver function is ing Lemma 1, (2k+2) (2k+1) Z+, hence 0 1 0) now defined as follows: for every And so a contradiction has been Structures reached. Therefore, s the greatest value that s not com Sequence can be stored in the variable xi putable by any program separates by using any halting program of two sequential statements Indefinite loop Rafael Morales-Bueno length exactly n, starting from while Xi 0 do Universidad de Malaga Let us show that (n) cannot Spain Statements be computed by a program in this Program language. We will adapt the proof References Lewis, H. R. and Papadi begin sketched out in [1] mitriou, C.H. Elements of the Theory of Computation statements. Prentice Hall, Englewood Cliffs, NJ LEMMA 1: For every n, S(n+I) end. 1981 (n) 2. M r. ALR. and Ritchie. D.M.Th (n) and let Notice that there are no Let us assume lexity of In Pro- OOP Programs. ceedings of the Twenty-Second ACM input/output operations in thi P be the corresponding program National Conference (1967), 465-169 language. In fact, xi is both the of n lines. Consider the 3. Rado, T. On noncom utable func- program P obtained from P by input and the output variable tions. Bell System Technical Journal The remaining variables-an adding the statement xi: xi+1 at indeterminate number are the end. The length of P is n+1 4. Sommerhalder, R., and van implicitly initialized to 0. In this Westrhenen, S.C. The Theory of Com- and xi reaches the value p+1 putability. Addison-Wesley, Woking hence X(n+1) p 1 >p X(n) way, a program P expresses a ham, England, 1988. functional relation between an 5. Wood, D. Theory of Computation. John input and an output, and a LEMMA 2: If f is computable by Wiley & Sons, New York, 1987 unique function from Z+ to Z+ can be associated with P Let P be the program that Example 1 computes Let us consider P begin obtained from P by adding n X2: X1 occurrences of X1:3 X1+1 at the while X2 0 do beginning. Starting from xi 0, it X1- X1+1 is obvious that P ends with X1 X2- X2 1 f(n). Since the length of P k+n, (n+k) f(n) od end. LEMMA 8: If P computes f and Q This program computes the func- computes g, then there is a progra tion f(x) 2x. that computes gef n fact, the statements of the In the text mentioned in [4], first program followed by the the following result is proved statements of the second program the class of functions that can be (variables renamed) make up a program that computes gof. computed by a program written in this language and the class of recursive functions are the same PROPOSITION: There is no program For this reason, this language is that oomputes the function Y. Assume that is computable. another formal substitute for the concept of "algorithm" and if f is f(x) 2x is computable example a function that cannot be com 1) and the composition of com puted by any program in th putable functions is also com language, then fis not com putable (Lemma 3). Then the function b(n) (2n) will be co putable. Augsat 1995/val. S8. Na 8Explanation / Answer
Busy beaver function Sigma(n) is the greatest value that can be stored in the variable X1 by using any halting
program of length exactly n.
Now, To completely understand, please understand all the lemma:
Lemma 1: It states that (n+1) > (n) i.e we got one more line and we just increment the value of X1 by 1.
Hence, 1 more line means 1 more increment and greatest value increases by 1.
Lemma 2: If it can compute f(n) in k steps, that means for every extra line we are getting, we can increment the value of X1 by 1 and hence (n+k)>=f(n) for all k. (equals when we choose not to increment x1 using the extra n lines).
Lemma 3: Obvious as g(f) can be computed using Q(P)
Now, from example 1 f(x)=2x is computable and since we have assumed is computable so by lemma 3
g(f) must be computable that is (2n) must be computable by say a program of length k.
Now apply lemma 2: (n+k) >= b(n) or (2n)
putting n=k+1 results in (2k+1)>=(2k+2) which directly contradicts Lemma 1.
HenceProved by contradiction.
DO THUMBS UP ^_^