Definition of Computability

Definition of Computability

Computability is a fundamental concept in theoretical computer science. It refers to whether a problem can be solved by an algorithm, which is a step-by-step procedure for calculations. An algorithm must produce a correct output for every valid input in a finite amount of time.

Formal Definition

A function is computable if there exists an algorithm that can compute the function's value for any given input from its domain. The domain is the set of all possible inputs for the function. If no such algorithm exists, the function is non-computable.

Types of Functions

Functions can be classified into computable and non-computable functions:

• Computable Functions: These functions can be calculated by an algorithm. For example, the function f(n) = n + 1 is computable because you can create an algorithm that takes an integer input n and returns n + 1.
• Non-Computable Functions: These functions cannot be computed by any algorithm. A well-known example is the Halting Problem, which asks whether a given program will finish running or continue forever. Alan Turing proved that no general algorithm can solve this problem for all possible program-input pairs.

The Halting Problem

The Halting Problem is a critical example in the study of computability. It can be stated as follows:

Given a description of an arbitrary computer programme and an input, determine whether the programme finishes running or continues to run indefinitely.

Turing showed that there is no algorithm that can solve this problem for all possible programmes and inputs. To understand this, consider the following:

1. Assume there exists a function H(P, I) that returns true if programme P halts on input I, and false otherwise.
2. Now, create a new programme G that uses H as a subroutine. The programme G takes an input X and behaves as follows:

if H(G, X) then loop forever else halt

When you run G with its own description as input, two cases arise:

• If H(G, G) returns true, then G will loop forever, contradicting the assumption.
• If H(G, G) returns false, then G halts, also contradicting the assumption.

Thus, the assumption that such a function H exists is false. Therefore, the Halting Problem is undecidable, meaning it cannot be solved by any algorithm.

Chomsky Hierarchy

The Chomsky hierarchy classifies languages based on their generative power. It consists of four levels:

• Type 0: Recursively enumerable languages, which can be recognized by a Turing machine.
• Type 1: Context-sensitive languages, which can be recognized by a linear-bounded automaton.
• Type 2: Context-free languages, which can be recognized by a pushdown automaton.
• Type 3: Regular languages, which can be recognized by a finite automaton.

This hierarchy is important in understanding the limits of computability and the types of problems that can be solved by different computational models.

Models of Computation

Several models of computation help to illustrate the concept of computability:

• Turing Machines: A theoretical model that defines an abstract machine capable of simulating any algorithm. It consists of a tape (infinite in both directions) and a head that can read and write symbols on the tape.
• Finite Automata: A simpler model that recognizes regular languages. It consists of states, transitions, and accepts inputs based on the current state.
• Pushdown Automata: A model that recognizes context-free languages. It has a stack to keep track of additional information.

Each of these models has its own strengths and weaknesses, but they all contribute to our understanding of what can be computed.

Conclusion

In summary, computability is a central concept in theoretical computer science. It defines whether a function can be computed by an algorithm. The Halting Problem serves as a key example of a non-computable function. Understanding the Chomsky hierarchy and models of computation helps clarify the limits and capabilities of computability.

Check your understanding

• What is the formal definition of computability?
• Explain the difference between computable and non-computable functions with examples.
• What is the Halting Problem and why is it significant?
• Describe the Chomsky hierarchy and its importance in computability.