This post describes why some problems are not solvable by programs (computers). Terms such as decidable,  recursively enumerable are introduced in context of programs.   The basic idea is that there are more problems than programs that can be constructed – Countability of sets is used to show that Section 1 .  Problems and programs can be encoded as strings  as we see in Section 2.  The limitations of programs is discussed in Section 3

1)  Sets – Countability

Countable  Sets  – are either finite or infinite.   {1,2,3} is a finite set. The set of integers is infinite.

Odd numbers, Fibonacci numbers  are countable  though infinite . The criteria for countability is that there must be one to one correspondance with integers.  the mapping function N=> N*2 + 1 establishes the correspondance between integers and odd numbers.

Uncountable Sets – These are the sets that cannot be put in one to one correspondance with integers. If you show a mapping function (from integers to this set) , then I can show a member of the set that doesn’t gets mapped to. Thus this set has larger than the set of integers

The power-set of a countably infinite  is uncountable.

Now countable and uncountable sets are used to show many things, for example
a)  the set of real numbers is larger than integers/rationals (the former is uncountable, the latter is countably infinite)
b)  there are more languages than programs ( the former is uncountable, the latter is countably infinite)
(read the section strings and languages)

2)  Strings and languages

Strings such as  SS = { a,b, aa,ab, ba, bb…..}  (called sigma-star) are also countable infinite as they can be put in correspondance with integers (they are just numbers in base-26)

A Language is a subset of strings (such as those containing equal number of a’s and b’s) .  the string  {0,0,0,1,1,0….} tells that only {ab,ba} are in EQUAL language. The number of languages is the number of binary strings possible . Binary strings define powerset . Thus languages are powerset of sigma-star .

Now sigma-star is countably infinite and its powerset is uncountable. Thus languages are uncountable

Now consider all possible programs. They can be encoded as strings. The set of programs is countably infinite

3)  Programs – Deciding and Recognizing :

consider the set E , the set of even numbers . We can write a program to  say whether a number/string is member of the set
or we can say if it is not  a member.  The membership of a number in the set is decidable.  The program that decides the membership will say
YES or NO and in both case it will HALT.  Consider the strings accepted by the program

f(int n)
{
if (n%2==0 ) return
else loop
}

These set of strings accepted is E and we can write a program check membership in E

Now consider a general program g

g(int n)
{
…some complex conditions and calculations….
}

say the set of strings accepted by g is G . Now how can I write a program to find whether a string is a member of G.
You can run g() on the input, When run with member of G ,  it accepts (say YES)
What happens if you give a non-member it may say NO or it may run forever/ doesn’t halt

sets such as E are called DECIDABLE ( both members and non-members are identified)
sets such as G are RECOGNIZABLE (  members can be identified , but non-members cannot be)
Note that if  a set and its complement are both RECOGNIZABLE , then the set is DECIDABLE

There are some sets which are NOT-RECOGNIZABLE ( even members cannot be identified) .
The set of strings accepted by g() is recognizable…but the set of strings not accepted by g() is not-recognizable. We cannot say if the program will halt on specific inputs..

Now suppose instead of checking whether a particular string is a member of G , we want to enumerate all members of G. One way to do is generate all strings in a sequence..{ a, b, aa,ab,ba, bb…. } Then run them in parallel by dovetailing  (you can think of it as time-slicing in OS ) and those that are accepted can be enumerated as members of G. Thus those that are RECOGNIZABLE can be made ENUMERABLE.
In mathematical function theory, RECOGNIZABLE languages are called RECURSIVELY ENUMERABLE and DECIDABLE LANGUAGES are called RECURSIVE

Set of strings define languages…Why are some languages not-recognizable .. This basic limitation comes because there are more languages than programs (related to uncountable/countably infinite) and thus some languages cannot be recognized. This means whatever we do , there are limitations on programs and some problems (abstractly checking membership on a language) are just unsolvable.