Problem 29 - Discrete Mathematics with Applications

Question

The 91 -function \(f\), invented by John McCarthy, is defined recursively on \(\mathbf{W}\) as follows.$$f(x)=\left\\{\begin{array}{ll}x-10 & \text { if } x>100 \\\f(f(x+11)) & \text { if } 0 \leq x \leq 100\end{array}\right.$$ Compute each $$f(f(99))$$

Step-by-Step Solution

Answer

The value of the given 91-function, \(f(f(99))\), is computed as 91.

Step 1: Compute the inner function (f(99))

Since the input value 99 is less than or equal to 100, we will use the second definition of the function: \(f(x)=f(f(x+11))\) Therefore, we must evaluate the function for \(f(99)=f(f(99+11))=f(f(110))\)

Step 2: Compute f(110)

Now, for the inner function, we have an input value of 110, which is greater than 100. Therefore, we will now use the first definition of the function: \(f(x)=x-10\) So, \(f(110)=110-10=100\)

Step 3: Compute f(f(99))

Now that we know the value of the inner function, we can substitute it back into the original expression to compute the final answer. \(f(f(99))=f(100)\)

Step 4: Compute f(100)

Finally, we need to compute the function for the input value 100. Since 100 is less than or equal to 100, we will use the second definition of the function: \(f(x)=f(f(x+11))\) Therefore, we must evaluate the function for \(f(100)=f(f(100+11))=f(f(111))\)

Step 5: Compute f(111)

Now, for the input value of 111, which is greater than 100, we will now use the first definition of the function: \(f(x)=x-10\) So, \(f(111)=111-10=101\)

Step 6: Compute f(f(100))

Now that we know the value of \(f(111)\), we can substitute it back into the expression for \(f(f(100))\). \(f(f(100))=f(101)\)

Step 7: Compute f(101)

Finally, we need to compute the function for the input value 101. Since 101 is greater than 100, we will use the first definition of the function: \(f(x)=x-10\) Therefore, \(f(101)=101-10=91\)

Step 8: Final Answer

After evaluating the 91-function recursively, we find that \(f(f(99))=91\).

Key Concepts

Discrete Mathematics

Discrete mathematics is a branch of mathematics that deals with objects that can assume only distinct, separate values. In contrast to continuous mathematics, which describes objects that can vary smoothly, discrete mathematics involves countable sets, such as integers or logical statements.
It finds applications in various fields such as computer science, cryptography, and network theory due to its focus on countable, often finite, sets. In the context of recursive functions, discrete mathematics provides a framework for defining functions with clear rules and finite steps.
This is crucial when computers execute functions, as they often utilize recursive algorithms in coding and data processing.

91-function

The 91-function is a famous recursive function discovered by John McCarthy. It is defined with two distinct cases depending on the range of the input value.

• For values greater than 100, the function simply subtracts 10 from the input.
• For values between 0 and 100, the function is defined recursively, which means that it calls itself.

This function is intriguing because despite the complex layers of recursion, it consistently converges to 91 for inputs 0 to 101. As demonstrated in the exercise, even starting with an input of 99, the final result is 91.
This peculiar property makes the 91-function both a fascinating study subject in understanding recursion and a useful test in theoretical computer science.

John McCarthy

John McCarthy was a pioneering American computer scientist known for coining the term 'artificial intelligence' and for his substantial contributions to the field of computer science.
Among his numerous innovations was the recursive 91-function, which elegantly demonstrates the power of recursion to solve complex problems. His work was critical in the development of the Lisp programming language, which is often used to define recursive functions and underscores the utility of recursion as a concept in programming.
McCarthy's influence extends throughout modern computing, with his principles and ideas forming the basis for later advancements in AI and automated reasoning.

Recursion in Mathematics

Recursion in mathematics is a method where a function is defined in terms of itself. This approach is invaluable for solving problems that can be broken into smaller, identical subproblems.
In recursive functions, a base case provides a condition under which the recursion terminates, preventing infinite loops. For instance, the classic mathematical puzzles like the Tower of Hanoi or the Fibonacci sequence are famously solved using recursion.
Recursive algorithms are essential in computer science for tasks such as sorting data, parsing expressions, and traversing structures like trees and graphs. The step-by-step solution of the exercise shows how recursion simplifies a seemingly complex problem by reducing it to simpler parts, effectively breaking it down with consistent logic.