Level 0, recursive and recursively enumerable languages

Finally, time for level 0. This is going to be a short one, because I've already talked about a lot of it in other posts:

Level 0 grammars are absolutely unlimited. Anything can be on the left or the right hand side the grammar. Rules can expand and contract the string; terminals can be replaced, etc. The only real distinction between non-terminals and terminals in a level 0 grammar is that you haven't generated a sentence in the language until there are no non-terminals left.

Machines for level 0 are turing machines (or any equivalent).

The main interesting thing that happens at level 0 is that you can describe two very important families of languages (and thus of functions) in terms of level 0 machines:

• The recursive languages
  
• The recursively enumerable languages
  

The recursive languages are the set of languages where given a string, a computing machine will eventually stop and answer "Yes" or "No" to indicated whether or not the string is in the language. The functions corresponding to the languages are known as recursive or computable functions.

The recursively enumerable languages are the set of languages where given a string, a computing machine will eventually stop and say "Yes" if the string is in the language. But it might never stop and say no. And at any point in time, if it hasn't stopped yet, you don't know whether it's eventually going to stop and say "Yes". So you can't be certain that a given string isn't in a language.

In function-oriented terms, a recursive function is one computable by a machine that always halts. A recursively enumerable function is a possibly partial function where a machine that computes it will never halt for some values; until the machine halts, you can never be sure that it won't; so you can't ever be certain that the value of the function for a given input is undefined.

So why do we call them recursively enumerable? Because there's a recursive function that generates the strings in a RE language. It doesn't test to see if they're in the language; it just generates strings, and given enough time, any string that's in the language will eventually be emitted.

There are two different ways of thinking about the process of recursively enumerating things; the grammar oriented approach, and the function oriented approach. The grammar one is harder to formalize completely, but it's easier to understand in principle.

The grammar approach is: given a grammar G, which consists of productions g_1, g_2, ..., g_n:

1. For every length L from 1 to infinity:
   
   1. Generate every possible permutation of rules g_i in G of length L.
      
   2. Apply the sequence of rules one at a time, if possible. (If not, then give up on that sequence.)
      
   3. If after applying the sequence of rules, the result is a string of terminals, print it out.
      

What makes it harder to really formalize this properly is that just generating the sequence of productions isn't enough - a given production can often be applied at more than one point in a string, and you need to make sure that you are exploring every possible application of each of the rule sequences.

The functional approach comes from recursive function theory. It's easier to write if I introduce a bit of formalism for it.

If we have a universal computing machine, we can treat it as a two parameter function: the first parameter is a program; and the second parameter is the input to the program. For some strange reason, it's traditional to call the function for the computing machine by the greek letter Phi written in script. I'll just write Phi. If the machine Phi is a turing machine of its equivalent, we call Phi an effective computing system.

For any effective computing system Phi, it's possible to list all of the possible programs for it - just take every possible program, and arrange them so that the shortest ones come first; and within programs of a given length, order them alphabetically. Once you've done this, you can assign a unique natural number to each program. This is called an effective numbering of the programs for Phi.

Once we've done this, we can define our function Phi for a computing device so that it's first parameter is an integer identifying a program according to the effective numbering.

So now, for instance, we can write Phi(3,7) to mean run program number 3 on Phi using 7 as the input.

Now, if Phi is a machine, we can define another function, PhiPrime, which takes three parameters, and returns either an integer, or a special value called bottom. The first two are, as in Phi, the effective program number and the input. The third is an integer. PhiPrime(x,y,z) runs program x on input y for z steps of Phi; if the program halts in "z" steps or less, then PhiPrime(x,y,z)=Phi(x,y); otherwise, PhiPrime(x,y,z)=bottom.

So - now, with all of that defined, we can finally describe how to enumerate the values for which a given program p will terminate.

1. For each natural number i > 0:
   
   1. for each natural number j less than i:
      
      1. if PhiPrime(p,i-j,j) != bottom, print (i-j)
         

So - first we run p(0) for one step.
Then we run p(0) for two steps, and p(1) for one step.
Then we run p(0) for three steps, and p(1) for two steps, and p(2) for one step.
And so on.

Eventually, for any combination of x and y, PhiPrime(p,x,y) will get run - so if Phi(p,x) halts, eventually, we'll emit x. If Phi(p,x) doesn't halt, it will never get emitted. But since there's no particular ordering to how the values get emitted, we don't ever know for sure if Phi(p,x) doesn't halt. We can say for any y we select that PhiPrime(p,x,y) doesn't halt - but it's always possible that PhiPrime(p,x,y+1) might.