Q8 2006

What examples would you suggest we use for Recursively enumerable languages and Recursive languages?

I'm actually a bit short on knowlege on this part, can't really remember what is what.

Hope you can give some ideas.

_______________________________________
Don't be different...be the one making a difference

r.e. Input goes to one of three: Accept(T), Loop(T), Reject(T)

The thing to remember there is Loop.

recursive is almost the same, but there's no loop.

So you need a language that loops forever on something for an r.e. (as well as being able to show the other two exhaust all the possibilities).

And with the recursive you must have one that can't loop eternally.

Is that enough to get you started?

Before you even think about that, I suppose the first thing to do is see if I'm talking nonsense again, eh? I seem to have gotten every question I look at back to front.

Just a thought. If you've done some question involving building a TM, you'll know how it behaves, right? So that would be one of your examples. If it has some eternal loop (like the perfectly good ba ba machine I was so puzzled about) then it's an example of an r.e. language.

Another thought. r.e. is the outermost circle of the Venn diagram, isn't it? (Better check that)

If it is, then you can take any language inside it, and you're r.e. Take some regular language, for instance.

Again, you might have examples lying around in the questions you've already answered.

In fact you probably just need an example of a recursive language? What do you think?

thanks eddy, you make it seem quite interesting, but perhaps a nice clean example will help make the link in my brain. What says you to that?

_______________________________________
Don't be different...be the one making a difference

Well for recursive you can't do much better than the example Cohen gives.

S ---- (a, a, R) ----> Halt

If your specification of L is simply that its words must start with a, how would you ever loop? I think that lack of a loop is intrinsic to a recursive language: That is to say you can stand on your head and whistle Dixie all day (what a magistrate I knew well used to love to tell an accused before whatever he had to say) and you still will not be able to loop.

I think so. I need to read a bit more to convince myself that this is so.

Thanks for that Eddy

And now a example for a R.E

Just put an infinite loop in that? (b, b, L) back to the start state. Same as in the other question. Because you've gone L on the tape you now know you're back on the initial a, which will take you R to b, which will take you L to a ...

"Words that start on a, but don't have b as their second letter" are now what is accepted.

Words that start on b crash, so we do have some crashes/ Reject(T). Everything you could ever want in a r.e. language.