Understanding Computability Theory

Computability Theory

• This area of study sits at the intersection of mathematical logic, computer science, and computation theory.
• It asks which problems are solvable using algorithms and which are not.
• Explores computation's limits and algorithm characteristics.
• Critical to computer science, mathematics and general knowledge.

Importance of Computability Theory

• Key to determining a computer's problem-solving capabilities, regardless of how powerful it is.
• Efficient algorithm design is fostered by studying the complexities inherent in various problems, focusing on time and space efficiency.
• Helps identify inherently difficult problems, allowing focus on more manageable ones.
• Develops a deeper understanding of computation and its limits.

Computability and Complexity

• Some fundamental problems are impossible for computers to solve.
• An example of an unsolvable computing problem is determining the truth of a mathematical statement.
• Complexity theory classifies problems by their difficulty, separating them into "easy" and "hard" categories.
• Computability theory classifies problems by solvability, distinguishing between what is solvable and what is not.

Computational Difficulty and Ease

• Computer problems vary in difficulty.
• Sorting problems tend to be "easy".
• Scheduling problems tend to be "hard".
• Computable functions can be calculated by an algorithm in a limited number of steps.

Recursion

• Recursion defines functions in terms of themselves.
• This feature allows complex algorithms and intricate problem solutions.
• Recursive functions need repetition control.
• The "if-else" statement in recursive functions determines return values and the function call itself.
• The depth of recursion is the number of times a function calls itself.

Recursion Example

• Example code shows a "factorial" function and its recursive call to itself

Recursion in Problem Solving

• Recursion is effective for solving repetitive problems.
• Recursion isn't essential since loops can also solve any recursively solvable problem.
• Recursive algorithms are often less efficient due to function call overhead.

Recursive Function Outline

• Repetitive problems are solved more easily through recursion and recursion.
• Base Case: The problem is solved without further recursion.
• Recursive Case: Reduces the problem into a simpler form and calls the function again.

Factorials

• Factorial of n (n!) is a mathematical notation.
• 0! = 1
• For n > 0, n! equals 1 x 2 x 3 …, multiplied by n.
• The factorial defition suits recursive programming.
• n = 0 is the base case.
• n > 0 is the recursive case.
• The formula for this is "factorial(n) = n * factorial(n-1)".

Recursive Processes

• Recursive calls reduce the problem until the base case is reached.
• Problems can be simplified with each function call by reducing parameters.

Recursion Types

• Direct Recursion: A function calls itself.
• The earlier examples are all of direct recursion.
• Indirect Recursion: Function A calls Function B, which calls Function A.

Recurring Algorithms: List Summation

• Lists can be summed recursively
• Functions receive lists to sum, and specifies an inclusive index range.
• An example of the base case is "if start index > end index return 0."
• An example of the recursive case is "return current_number + sum(list, start+1, end)."

Recursive Algorithm Example

• Example pseudo code and function call of range_sum, with the conditions

Fibonacci Sequences

• Fibonacci series has two base cases: if n = 0 then Fib(n) = 0, and if n = 1 then Fib(n) = 1.
• A corresponding function code is if n > 1 then Fib(n) = Fib(n-1) + Fib(n-2).

Greatest Common Divisor

• GCD, the greatest common divisor, is calculated for two positive integers.
• A condition for the function is if x can be evenly divided by y, then gcd (x, y) = y.
• Else, gcd (x, y) = gcd (y, remainder of x/y).

Towers of Hanoi

• Mathematical game to demonstrate recursion power.
• Requires three pegs and decreasing sized discs.
• The goal of the game is to move discs from the leftmost to the rightmost peg.
• Only one disc move at a time.
• Discs cannot be placed on smaller discs.
• Discs must be on peg during moves.

Towers of Hanoi Problem Statement and Solution

• The problem statement is moving n discs from peg 1 to peg 3.
• Peg 2 is used as a temporary peg.
• Move disc 1 to 3 where n = 1.
• Move n-1 discs from peg 1 to peg 2 with peg 3.
• Move the remaining disc from peg 1 to peg 3.
• Move n-1 discs from peg 2 to peg 3 with peg 1.

Towers of Hanoi example code

• Contains example lines of code calling the move_disc function, its conditions and arguments

Recursion vs Looping

• Recursion can have overheads such as function call overhead.
• Loops solutions are often more obvious than recursive solutions.
• A loop is repeatedly executing an instruction until filled.
• Some problems are easier with recursion, like Fibonacci sequences.
• Recursion doesn’t need initial conditions.

Recursive Functions

• Total recursive functions have a defined output for every possible input value.
• If f(a1, a2, ...an) is defined on g(b1, b2, ...bn), then f is total if every element is assigned a unique element in g.
• Additionally, a total function is considered recursive or primitive recursive if it starts as an initial function over n.
• Also if it undergoes composition/recursion a finite number of times from the function over n.

Total or Primitive Recursive Functions

• Multiplying two positives is a total or primitive recursive function.
• Not all total recurisve function are primitive.
• All primitive functions have a total function.
• Functions like n! and logn are total recursive functions.

Partial Recursive Functions

• Functions computed by a Turing Machine (TM) are considered partial recursive functions.
• Let function f(a1, a2, ...an) be defined on g(b1, b2, ...bn) where if f is defined for some, but not all values.
• f is considered a partial function when elements of f are assigned to almost one element of function g.

Recursive Applications

• Partial functions are recursive if it begins as a function over N.
• This occurs when applying recursion, composition of minimization over N.
• Functions such as subtraction are considered partial recursive functions.
• Composing partial or total functions will provide the corresponding function.
• Minimizing a total function will give a partial function.

Recursively Enumerable Recursive Languages

• Recursively enumerable languages have subsets in the alphabet of a language.
• Any Turing machine, whether in standard configuration or other is recursively enumerable.
• A language is Recursively Enumerable if a Turing Machine can accept input.

Enumerable Recursive Languages cont.

• Recursively enumerable languages can be "decided" in full or in part.
• Based on the Chomsky hierarchy, recursively enumerable languages equate to Type 0.
• Examples of recursively enumerable languages include; recursive languages, regular/context sentitive languages, and context-free languages.

Recursive Languages

• A language L is recursive or decidable if it uses a Turing Machine that stops at all inputs.
• Halting can occur at a final state, or when a state q and the current symbol ‘a’ are undefined.
• There are machines that never halt on certain inputs.
• Therefore a distinction is made between languages that halt on all input strings, or never halt on particular inputs.

Recursively Enumerable Languages

• Language L is recursively enumerable if a Turing Machine is used.
• In which case, function w ∈ L leads to a final state.
• When w∉ function L and halts in a non-final state, or loops forever.
• Likewise, for recursive languages, function w ∈ L halts in a final state.
• If w ∉ L is met by halting in a non-final state.

Recursive Enumerable Properties

• Recursive languages are recursively enumerable.
• Proof: If L is recursive, then a Turing Machine decides a member in a language
• M accepts x if x belongs to a language L.
• M rejects x if x does not belong to a language L
• Per the definition, a machine can recognize strings accepted in those languages.