### 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 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

In function-oriented terms, a recursive function is one computable by a machine that always halts. A recursively enumerable function is a

So why do we call them recursively enumerable? Because there's a recursive function that

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:

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

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

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

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

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

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

*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:

- For every length L from 1 to infinity:

- Generate every possible permutation of rules g_i in G of length L.

- Apply the sequence of rules one at a time, if possible. (If not, then give up on that sequence.)

- If after applying the sequence of rules, the result is a string of terminals, print it out.

- Generate every possible permutation of rules g_i in G of length L.

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.

- For each natural number i > 0:

- for each natural number j less than i:

- if PhiPrime(p,i-j,j) != bottom, print (i-j)

- if PhiPrime(p,i-j,j) != bottom, print (i-j)

- for each natural number j less than i:

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.
## 1 Comments:

Hello!!! I'm lookng for a proof related to the closure properties of the recursively enumerable laguages (concatenation and Kleene star), and i thought that you can help me to find them.

Thanks very much.

My email is miramire@gmail.com

By Miltoco, at 12:31 AM

Post a Comment

## Links to this post:

Create a Link

<< Home