# Gödel-Numbering of the Context-Sensitive Languages

I would like to have a Gödel-numbering of the context-sensitive languages. Because there is no obvious syntactic distinction between LBAs and TMs, I cannot number the former in an immediate way. So I thought of CS grammars, but I do not think there is a bound on the alphabet size (the number of non-terminals).

Now I still think I could do it for example like this: look at TMs where the left and right ends of the input are marked and there are no transitions crossing these borders. But writing this down would be a bit of an effort, which has nothing to do with my real topic.

Therefore I am looking for some reference for a Gödel-numbering of the context-sensitive languages, which I could cite instead of working out all the details myself.

• Why don't you simply assume that the endmarkers and "bounce" transitions (or "halt" transitions) on them are part of the computational model and use the same Godel-numbering of TMs? – Marzio De Biasi Jul 24 at 11:46
• Well, @MarzioDeBiasi, as I have said, I could do something like what you are proposing. But I would have to specify the model exactly and spend some time/space on the argument. On the other hand, my feeling is that somebody must have used a Gödel numbering of CS somewhere. Just referencing this would save me doubts as to what level of formal detail is necessary etc. Because I have not been able to find any reference, I ask here, if anybody can point me to some. If not, I will try to come up with an as-easy-and-compact-as-possible solution myself. – Peter Leupold Jul 24 at 11:59
• @PeterLeupold What exactly do you mean by Gödel-numbering all context-sensitive languages? A CSL is an infinite set in general. It's trivial to Gödel-number CS grammars, but a CSL can be denoted by more than one CSG (or LBA or TM). – Martin Berger Jul 24 at 12:20
• @PeterLeupold Such an understanding is probably never spelled out in detail, because it's rightly assumed to be straightforward. – Martin Berger Jul 24 at 14:21
• Also, the unbounded number of non-terminals is a non-issue. There are unboundedly many numbers, finite strings, Turing machines, etc., but these can all be easily coded as finite sequences of bits, which are just natural numbers in binary. So what's the issue? – Andrej Bauer Jul 25 at 11:51

• And again, the worries unboundely many non-terminals are a complete non-issue. All you ever do with non-terminals is to compare them. So, how about if you just use numbers 0, 1, 2, ... for the terminals? What's going to go wrong? – Andrej Bauer Jul 25 at 22:01