In-Depth Analysis of Recursive Functions and Set Theory Concepts

This assignment delves into the concepts of recursive functions and set theory, providing detailed solutions and explanations. It begins by analyzing the Ackermann function, demonstrating its behavior for specific inputs and proving its properties using mathematical induction. The assignment then explores recursive definitions of sets, proving that a given set possesses a certain property P based on its recursive structure. Furthermore, it examines formal languages, identifying strings with specific characteristics, such as an even number of zeros. Finally, the assignment investigates sets generated through recursive processes, proving that all elements of a particular set end with the digit 6. This comprehensive analysis offers a thorough understanding of recursive functions, set theory, and their applications in computer science. Desklib provides access to this and many other solved assignments for students.

Question 1
a) A ( m ,n )=¿
For A(1 , n), m=1 hence for all positive integers i.e. n ≥ 1, we have
A ( 1 , n )= { 2 for n=1
A ( 0 , A (1 , n−1 ) ) for n ≥ 2
But A ( m ,n )=2 n if m=0 hence A ( 0 , A ( 1 ,n−1 ) )=2 n for n ≥2.
Therefore, A ( 1 , n ) = { 2 for n=1
2 n for n ≥ 2
By induction, we show that if A(1 , k ) holds, then A(1 , k +1) also holds where
A ( 1 , k )=2k for k ≥1
We show that the statement holds for k =1.
A ( 1,1 )=21=2 which is equal to the previous calculation.
Assume that A ( 1 , k ) holds, then we show that A(1 , k +1) holds
i.e show that 2 ( k +1 ) =2(k+1 )
For k ≥ 2 A ( 1 , k +1 ) = A(0 , A (1 , k+ 1−1))
¿ A ( 0 , A ( 1 ,k ) )= A ( 0 , 2k )
¿ 2(2k )
Hence A ( 1 , k +1 )=2k +1 proving that A ( 1 , n )=2n for all positive integers
b) a↑↑1=aa
a ↑ ↑ ( k +1 ) =aa( k+ 1)
¿ aa(ak)
¿ aa( a¿¿k) ¿
We can define a(ak) as a ↑ ↑ k hence we have
a ↑ ↑ ( k +1 )=aa ↑↑ k
c) A ( 2 , n )= { 2 for n=1
A ( 1 , A ( 2 , n−1 ) ) for n ≥2
Solving by induction, we prove that for all positive integers, i.e. n ≥ 1, A ( 2 , n ) =2 ↑↑ n
Show that if A ( 2 , k ) holds, then A( 2, k +1) also holds
For k =1, A ( 2,1 )=2 which holds since 2 ↑↑ 1=2
For k =2, A ( 2,2 )= A ( 1 , A ( 2,1 ) )= A ( 1,2 )=2 n=4
For k ≥ 2 , A ( 1 , k +1 )= A ( 1 , A ( 2 ,k ) ) where A ( 2 , k ) =2 ↑↑ k
Since values of 2 ↑↑ k are greater than 2, A ( 1 , A ( 2 , k ) ) =2∗2 ↑ ↑k hence at
k +1 , A ( 1 ,k + 1 ) =2 ↑↑(k +1) proving that (2, 𝑛) = 2 ↑↑ 𝑛 for all positive integers 𝑛.

d) A ( 3 , n )= { 2 for n=1
A ( 2 , A (3 , n−1 ) ) for n ≥ 2
From (c) above, A ( 2 , n )=2 ↑↑ n hence, A ( 3 , n ) =2 ↑ ↑ A( 3 ,n−1)
Where A ( 3 , n−1 ) =A ( 2 , A ( 3 , n−2 ) )
¿ 2 ↑↑ ↑ A ( 3 , n−2 )
¿ 2 ↑↑(2 ↑↑ A ( 3 , n−3 ))
Continued expansion of the series leads to generation of an equation of the form
A ( 3 , n )=2 ↑ ↑↑ n
Proof by induction
We show that if A ( 3 , n ) holds, then A ( 3 , n+1 ) also holds for all positive integers.
We assume it is true for the base integer, 1.
For n=1, A ( 3 , n )=2 which is true since 2 ↑↑ ↑1=2
For n+1, A ( 3 , n+1 ) = A (2,2↑ ↑↑ n) but A ( 2 , n )=2 ↑↑ n hence we have
A ( 3 , n+1 )=2 ↑↑ ( 2 ↑↑ ↑ n )=2 ↑↑ ↑(k +1), proving that it is true for n+1
Question 2
Recursive definition of base case and recursive step.
For this case, the base case is 2 ∈ S and the recursive step is
if n ∈ S , then2 n ∈ S
if n ∈ S , then n2 ∈ S
Let x be a member of S i. e x=2p , p ∈ N
Let y be an arbitrary member of S
Then, either y=2 x or y=x2
If y=2 x, then y=2 x=2∗2p=2p +1∈S
So y=2p+1 , p ∈ N ∈ S
If ¿ x2 , then y=x2=( x p)2= x2 p ∈ S
So y=x2 p , p ∈ N
Hence y also has theform y=2k for k ∈ N . Since y is arbitrary, we conclude that S has the
property P, proving the statement.

Question 3
B={010,00010,0101,0000010,000101,000101 , … }
Clearly, 010 is of length 3 and has an even number of zeros.
For any x ∈ B, assume that it has even number of zeros. Then x produces two strings 00 x , x 1in
B where they all have even number of zeros hence every element contains even number of zeros.
Question 4
Each element of S is given by a finite level of recursion from 6 in two steps
When the level of recursion k =0,we get only 6 ∈ S which clearly ends with 6
When k =1, we get 2 elements: 62 =36 and 3∗6−2=16. Clearly both elements end with 6.
We show that all elemnts of S obtained by k levels of recursion end with 6. Suppose n is any
element of S obtained by (k + 1) level of recursion. Then, n=3 m−2 or n=m2 for some number m
ending with 6;
We use the algebraic definition m=10 z +6 for some non-negative integer z.
When n=3 m−2=3 ( 10 z+ 6 )−2
¿ ( 3 z+1 )∗10+6 which ends with 6
When n=m2=(10 z +6)2=100 z2+120 z +36 which ends with 6. Thus all elements of S obtained
by any level of recursion are numbers ending with 6.
References
Bluman, A. G. (2001). elementary statistics with CDROM. McGraw-Hill Companies.
Triola, M. F. (2014). elementary statistics. Pearson.