<p>"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."</p>

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

CC BY-SA 4.0
2019-07-25T14:38:15.793Z
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.
Peter Leupold
CC BY-SA 4.0
2019-07-25T14:49:45.387Z
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?)
Martin Berger
CC BY-SA 4.0
2019-07-25T22:00:04.073Z
Indeed, until you tell us *what* you need the encoding for, we have no criterion to judge its correctness.
Andrej Bauer
CC BY-SA 4.0
2019-07-25T22:01:55.607Z
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
CC BY-SA 4.0
2019-07-25T11:43:58.823Z
2019-07-25T11:43:58.823Z
Andrej Bauer
<p>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). </p>

<p>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.</p>

<p>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.</p>

CC BY-SA 4.0
2019-07-24T11:46:51.450Z
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
CC BY-SA 4.0
2019-07-24T11:59:47.810Z
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
CC BY-SA 4.0
2019-07-24T12:20:07.110Z
@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
CC BY-SA 4.0
2019-07-24T12:25:54.913Z
You are right, @MartinBerger, my question is not really corrext: I am really looking for a formalism for CS that is easily Gödel-numbered or rather one for which this has been done + reference. However, I do not think that CS grammars are such a formalism. For the numbering you need a fixed alphabet for your model. But CS grammars can have arbitrarily many non-terminals. I have not been able to find a normal form with a fixed number - such a result would also be an answer to my question.
Peter Leupold
CC BY-SA 4.0
2019-07-24T12:33:59.987Z
@PeterLeupold Size of the alphabets is not really a problem, you can simply put them as part of the component. So a CS grammar is something like this tuple $(m, n, (l_1, r_1), ..., (l_k, r_k))$  where $m$ is the size of the terminals, $n$ the size of the non-terminals, and the $(l_i, r_i)$ the rewrite rules. This can be handled with standard encodings of tuples and lists.
Martin Berger
CC BY-SA 4.0
2019-07-24T14:01:58.740Z
Sure @MartinBerger, such an encoding is possible. But defining and explaining it will take quite a bit of space and time. My question is not a demand for technical help but rather for a reference, which could avoid the technical part, which has nothing to do with what I am working on.
Peter Leupold
CC BY-SA 4.0
2019-07-24T14:21:04.147Z
@PeterLeupold Such an understanding is probably never spelled out in detail, because it's rightly assumed to be straightforward.
Martin Berger
CC BY-SA 4.0
2019-07-25T11:46:48.693Z
But *why* do you want to explain the details? If the details really matter, you should be writing programs, not encoding things with Gödel numbers.
Andrej Bauer
CC BY-SA 4.0
2019-07-25T11:51:17.463Z
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
<reference-request><fl.formal-languages><computability><decidability>
Gödel-Numbering of the Context-Sensitive Languages
Peter Leupold
# Gödel-Numbering of the Context-Sensitive Languages

(Asked by: username_0 on 2019-07-24)

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.

**Tags:** reference-request, fl.formal-languages, computability, decidability

> **Comments:**
> **username_1**: 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?  
> **username_0**: 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.  
> **username_2**: @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).  
> **username_0**: You are right, @MartinBerger, my question is not really corrext: I am really looking for a formalism for CS that is easily Gödel-numbered or rather one for which this has been done + reference. However, I do not think that CS grammars are such a formalism. For the numbering you need a fixed alphabet for your model. But CS grammars can have arbitrarily many non-terminals. I have not been able to find a normal form with a fixed number - such a result would also be an answer to my question.  
> **username_2**: @PeterLeupold Size of the alphabets is not really a problem, you can simply put them as part of the component. So a CS grammar is something like this tuple $(m, n, (l_1, r_1), ..., (l_k, r_k))$  where $m$ is the size of the terminals, $n$ the size of the non-terminals, and the $(l_i, r_i)$ the rewrite rules. This can be handled with standard encodings of tuples and lists.  
> **username_0**: Sure @MartinBerger, such an encoding is possible. But defining and explaining it will take quite a bit of space and time. My question is not a demand for technical help but rather for a reference, which could avoid the technical part, which has nothing to do with what I am working on.  
> **username_2**: @PeterLeupold Such an understanding is probably never spelled out in detail, because it's rightly assumed to be straightforward.  
> **username_3**: But *why* do you want to explain the details? If the details really matter, you should be writing programs, not encoding things with Gödel numbers.  
> **username_3**: 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?  

---

## 1 answers

### Answer by username_3 on 2019-07-25. Score: 2

"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.

> **Comments:**
> **username_0**: 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.  
> **username_2**: 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?)  
> **username_3**: Indeed, until you tell us *what* you need the encoding for, we have no criterion to judge its correctness.  
> **username_3**: 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?  

---

