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.

  • 1
    $\begingroup$ 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? $\endgroup$ Jul 24, 2019 at 11:46
  • $\begingroup$ 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. $\endgroup$ Jul 24, 2019 at 11:59
  • $\begingroup$ @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). $\endgroup$ Jul 24, 2019 at 12:20
  • 6
    $\begingroup$ @PeterLeupold Such an understanding is probably never spelled out in detail, because it's rightly assumed to be straightforward. $\endgroup$ Jul 24, 2019 at 14:21
  • 2
    $\begingroup$ 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? $\endgroup$ Jul 25, 2019 at 11:51

1 Answer 1


"We use a suitable Gödel numbering of descriptions of context-sensitive grammars. For example, a context-sensitive grammar may be represented by a string of characters in some accepted formalism. Obviously, such a string is represented by a finite sequence of bits in computer memory, which is the Gödel code in question."

This will do in a research paper (we're on a research-level forum), nobody has any doubts about Gödel encoding.

  • $\begingroup$ I have been asked by referees to elaborate in more detail on questions at least as simple as this one. This is why I have asked for a reference to be able to avoid this; a proposal for the technical elaboration is already contained in the OP and is not an answer. I think that "an accepted formalism" normally has a fixed alphabet as have symbol encodings on computers. Therefore there seem to exist cs grammars that cannot be represented directly, only with another encoding as proposed in a comment above. There are many people who do not accept treating matters like this with a quick comment. $\endgroup$ Jul 25, 2019 at 14:38
  • $\begingroup$ What are you doing with the encoding? Depending on the precise questions you are tacking, the precise nature of the encoding might in fact matter. Usually the precise nature doesn't matter (e.g. in Goedel's incompletness proofs), but one can ask questions where is does matter (eg.. is 1382 the encoding of a CSG?) $\endgroup$ Jul 25, 2019 at 14:49
  • 1
    $\begingroup$ Indeed, until you tell us what you need the encoding for, we have no criterion to judge its correctness. $\endgroup$ Jul 25, 2019 at 22:00
  • 2
    $\begingroup$ 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? $\endgroup$ Jul 25, 2019 at 22:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.