Definition of Decidable.

We say that a language L is decidable if there exists a machine M such that,
given any input string w, M halts and outputs a single bit, which is 1 if
w is a member of L, and 0 if w is not a member of L.  You may think of M
as being a computer program written in your favorite programming language.

Otherwise, we say that L is undecidable.

A 0/1 problem is defined to be a problem where the answer is either 0 or
1, i.e., true or false.  Every 0/1 problem P can be considered to be
a language L_P as follows:

	1.  Think of some way to encode instances of P as strings.
	2.  Define L_P to be the set of all encodings of true instances of P.

Example: take P to be the problem: is a particular string generated by a 
particular context-free grammar?  In order to turn this problem into a
language, we first restrict it by insisting that the alphabet of terminals
is the binary alphabet, {0,1}.  This is not a real restriction, since
any alphabet can be encoded using the binary alphabet.  Next, we decide on
a way to encode any context-free grammar G as a string of binary symbols, 
which we call <G>.  This is not difficult.  We make sure that <G> ends
with a unique "end-of-file" string, such as 111111, which occurs nowhere
else in <G>.  We now define L_P to be the set of all strings of the form
<G>w such that w is generated by G.

The problem described above is called the context-free grammar membership
problem.  It is decidable.  In fact, if you have taken CSC 477, you could
easily write a computer program that decides it.  Not counting debugging,
it shouldn't take you more than a day to write that program.  (A truly
skilled professional programmer, using an advanced language, could write
the program in less than an hour, I would guess.)

The general grammar membership problem is undecidable.  A book that was
popular some years ago, "Goedel, Escher, Bach," contains an instance of
a version of the general grammar membership problem and challeges the reader
to solve it.  It is amazing to the reader that a problem that is so easy to
state can be so hard to solve, but that's one of the things we will discuss
in this course.