Computability and Complexity/Computability/Decidability

Decidability

This section discusses the decidability of problems run on Turing machines (TMs). For the definition of a Turing machine, see Unrestricted Languages.

Turing Recognizability

Those languages for which there is a Turing machine that will always halt and accept in a finite amount of time for any string in the language are called Turing recognizable languages. Note that it need not be possible to make a machine that halts and rejects all strings not in the language - the machine may loop. Continuing the previous example, the language composed of all {strings giving instructions (with some specific encoding) on how to produce and print as a decimal a number with a finite number of decimal places} is Turing recognizable. If a machine is given a correct input, it can follow the instructions, print the number, finish, and accept. If it is given instructions that don't make sense, it can reject. But if it is given instructions that look right, and follows them, it will run forever.

Decidability

There are some languages for which a Turing machine can be written that will halt on all input, either to accept or reject. These languages are called decidable languages, and TMs that always halt on any input are called Deciders. One example of a decidable language is the language whose words each consist of a stringified LBA together with an input string, where the LBA halts on that input. A TM can be written to emulate an LBA, recording the number of steps it makes, and accept if it accepts, reject if it rejects, and reject if it exceeds a certain number of steps (what that number of steps is and how it guarantees that the LBA will loop forever are explained in the chapter on Context Sensitive Languages). All decidable languages are also by definition Turing recognizable.

The Halting Problem

Perhaps the most important undecidable problem for a TM is known as the halting problem. A universal Turing machine (UTM) cannot always accurately predict whether a given TM will halt or run forever on a given input. Clever programming of the UTM can sometimes predict the answer, but the only solution for all problems is to emulate the machine on the input. Unfortunately, if the emulated machine runs forever, so will the UTM, and will never halt and reject. It has been proven that no TM can be written that can decide the halting problem, so the language consisting of stringified TMs with input strings, where the machine halts on that input string is a Turing recognizable language, but is not decidable.

Non-Recognizability

Not all languages can even be recognized. Take, for example, the inverse of the halting problem, the language whose words consist of a stringified TM with an input string, where the TM does not halt on that input. If that language was Turing recognizable by some TM 'S', then a UTM 'T' could be designed to emulate S, and to also emulate the TM being fed to S. Eventually, one of the two will halt, and thus T will be a decider for the halting problem, which we know doesn't exist, so the language is not Turing Recognizable. Furthermore, since every Turing Machine can be encoded as a unique string under some encoding, and there are a countably infinite number of strings, but an uncountably infinite number of languages, there must be an uncountably infinite number of languages to which there is no corresponding TM, and thus are not Turing Recognizable.

Previous | Next