let this be string N of the lan guage;
}
remove the string from set W;
}
4.4.4 Non-recur sively Enumerable Lan guages
A Language is a subset of Σ
* . A language is “any” subset of Σ
* . We have
shown that Turing machines are enumerable. Since recursively enumerable
laguages are those whose strings are accepted by a Turing machine, the set of
recursively enumerable languages is also enumerable. The power set of an
infinite set is not enumerable i.e., it has more than χ 0 subsets. Each of these
subsets represent a language. Hence there should be languages that are not
computable by a Turing machine.
According to Turing Thesis, a Turing machine can compute any effective
procedure. Therefore there are languages that cannot be defined by any
effective procedure. It is possible to find a non-recursively enumerable
language X by a process called “diagonalisation”.
4.5 UNDECIDABILITY
4.5.1 Halting Prob lem
The input to a Turing machine is a string. Turing machines themselves can be
written as strings. Since these strings can be used as input to other Turing
machines.
A “Universal Turing machine” is one whose input consists of a
description M of some arbitrary Turing machine, and some input w to which
machine M is to be applied, we write this combined input as M + w. This
produces the same output that would be produced by M. This is written as
Uni ver sal Turing Machine (M + w) = M (w).
As a Turing machine can be represented as a string, it is fully possible to
supply a Turing machine as input to itself, for example M (M). This is not even
a particularly bizarre thing to do for example, suppose you have written a C
prettyprinter in C, then used the Prettyprinter on itself. Another common usage
is Bootstrapping—where some convenient languages used to write a minimal
compiler for some new language L, then used this minimal compiler for L to
write a new, improved compiler for language L. Each time a new feature is
added to language L, you can recompile and use this new feature in the next
version of the compiler. Turing machines sometimes halt, and sometimes they
enter an infinite loop. A Turing machine might halt for one input string, but go
into an infinite loop when given some other string.
The halting problem asks: “It is possible to tell, in general, whether a given
machine will halt for some given input?” If it is possible, then there is an
Turing Machines
199
}
remove the string from set W;
}
4.4.4 Non-recur sively Enumerable Lan guages
A Language is a subset of Σ
* . A language is “any” subset of Σ
* . We have
shown that Turing machines are enumerable. Since recursively enumerable
laguages are those whose strings are accepted by a Turing machine, the set of
recursively enumerable languages is also enumerable. The power set of an
infinite set is not enumerable i.e., it has more than χ 0 subsets. Each of these
subsets represent a language. Hence there should be languages that are not
computable by a Turing machine.
According to Turing Thesis, a Turing machine can compute any effective
procedure. Therefore there are languages that cannot be defined by any
effective procedure. It is possible to find a non-recursively enumerable
language X by a process called “diagonalisation”.
4.5 UNDECIDABILITY
4.5.1 Halting Prob lem
The input to a Turing machine is a string. Turing machines themselves can be
written as strings. Since these strings can be used as input to other Turing
machines.
A “Universal Turing machine” is one whose input consists of a
description M of some arbitrary Turing machine, and some input w to which
machine M is to be applied, we write this combined input as M + w. This
produces the same output that would be produced by M. This is written as
Uni ver sal Turing Machine (M + w) = M (w).
As a Turing machine can be represented as a string, it is fully possible to
supply a Turing machine as input to itself, for example M (M). This is not even
a particularly bizarre thing to do for example, suppose you have written a C
prettyprinter in C, then used the Prettyprinter on itself. Another common usage
is Bootstrapping—where some convenient languages used to write a minimal
compiler for some new language L, then used this minimal compiler for L to
write a new, improved compiler for language L. Each time a new feature is
added to language L, you can recompile and use this new feature in the next
version of the compiler. Turing machines sometimes halt, and sometimes they
enter an infinite loop. A Turing machine might halt for one input string, but go
into an infinite loop when given some other string.
The halting problem asks: “It is possible to tell, in general, whether a given
machine will halt for some given input?” If it is possible, then there is an
Turing Machines
199