<blockquote>
  <p>It's possible to do a Gödel numbering that assigns every term in System F to a unique natural number? </p>
</blockquote>

<p>The answer is yes, pick your favorite way of coding terms in F, simply because they are countable number of expressions. </p>

<p>Just being able to assign numbers to expressions in a system is not useful by itself, the question is can it be done in a manner that supports some operations, e.g. substitution, inside the system. The answer is again yes, the standard one works, operations are computable in Girard's F. </p>

<blockquote>
  <p>Can we say that Church encoding is a form of Gödelization?</p>
</blockquote>

<p>Church encoding is an encoding of <em>natural numbers</em> by lambda terms, it is not an <em>arithmetization of a language</em> (the correct terminology is arithmetization not Godelization). For arithmetization of a language we need some way of representing natural numbers in a language, but that is independent of the arithmetization of the language itself. </p>

<p>But really the more important question is why would one want to arithmetize a language? Godel does it to be able to talk about the language itself in arithmetic and perform computation over the language. If you think about it what we really want is to talk about computation of functions over the syntactic expressions of a language, and we arithmetize because arithmetic can only talk about numbers. It is just a way of representing language expressions as numbers so we can talk about computation over them, the same way we encode language, numbers, graphs, etc. as binary strings when we deal with computers. Arithmetization was ingenious at the time of Godel, but now it is kind of trivial (in a sense) for a computer programmer. We can encode a formal language as numbers and perform computation over it, sure.</p>

<p>Finally, if you can arithmetize language in a system, you can arithmetize langauge in any system extending it. The syntactic constructions that one is interested do not change from say PA to Godel's T to Girard's F.</p>

CC BY-SA 3.0
2016-04-02T16:10:24.340Z
2016-04-02T16:22:39.647Z
2016-04-02T16:22:39.647Z
Kaveh
<p>We see <a href="https://cs.stackexchange.com/a/6889/1709">here the following statement</a> about Godelization:</p>
<blockquote>
<p>Gödel numbering in computer science means more or less &quot;source code&quot; and &quot;data in binary format&quot;, so I hope the significance of this should be obvious if I can convince you that this really is so.</p>
<p>Before modern computers came into existence, people made single-purpose computing devices (I am telling you a story, not a history), for example someone made a machine for calculating arctanarctan, and someone else made a machine for calculating the Bessel function. Turing's original insight was that we only had to build one machine (the universal one), which took as input the description of any machine and simulated it. But what is a &quot;description of a machine&quot;? An engineer might think of circuit designs and assembly instructions. But that is very complicated and not easily presented to a machine. And perhaps ever more complicated machines require ever more complicated descriptions?</p>
<p>We need a way of describing machines that is as simple as possible. Here Gödel's idea was important: he showed some years before Turing that all sorts of things in logic (formulas, proofs) could be encoded with numbers, and then manipulated within arithmetic. We can do a similar trick with Turing machines: encode the program, the current state, and the contents of the tape used so far, with a string of symbols on a tape (for examples 00's and 11's), and then manipulate the string with a Turing machine.</p>
</blockquote>
<p>We see <a href="https://en.wikipedia.org/wiki/Church_encoding" rel="nofollow noreferrer">here the following explanation of Church-encoding</a>:</p>
<blockquote>
<p>In mathematics, Church encoding is a means of representing data and operators in the lambda calculus. The data and operators form a mathematical structure which is embedded in the lambda calculus. The Church numerals are a representation of the natural numbers using lambda notation. The method is named for Alonzo Church, who first encoded data in the lambda calculus this way.</p>
<p>Terms that are usually considered primitive in other notations (such as integers, booleans, pairs, lists, and tagged unions) are mapped to higher-order functions under Church encoding. The Church-Turing thesis asserts that any computable operator (and its operands) can be represented under Church encoding. In the untyped lambda calculus the only primitive data type is the function.</p>
</blockquote>
<p><a href="https://stackoverflow.com/a/18403442/15441">This statement appears</a> to combine to two in a way that says they're orthogonal (ie that being church-encoded or not is irrelevant to the Gödelization process) - but I'm not sure:</p>
<blockquote>
<p>So let's say that you have natural numbers (or a Church encoding of natural numbers) in your typed lambda calculus. It's possible to do a Gödel numbering that assigns every term in System F to a unique natural number.</p>
</blockquote>
<p>My question is: <strong>Can we say that Church encoding is a form of Gödelization?</strong></p>

CC BY-SA 3.0
2016-04-02T08:57:16.367Z
Is there a scientific question here? It seems awfully vague to ask this question. For instance, why would "Yes we can" be an insufficient answer?
Andrej Bauer
CC BY-SA 3.0
2016-04-02T09:35:33.137Z
Perhaps with an illustration of why you can and a pointer to further reading. Some reasoning would be good too. Perhaps even pointing out flaws in the authors understanding might help.
hawkeye
CC BY-SA 3.0
2016-04-02T19:17:36.230Z
Well, in that case this question should be asked at cs.stackexchange.com. There's nothing research-level about it.
Andrej Bauer
<functional-programming><compilers><encoding><church-turing-thesis>
Can we say that Church encoding is a form of Gödelization?
hawkeye
# Can we say that Church encoding is a form of Gödelization?

(Asked by: username_0 on 2016-04-02)

We see [here the following statement](https://cs.stackexchange.com/a/6889/1709) about Godelization:

> Gödel numbering in computer science means more or less "source code" and "data in binary format", so I hope the significance of this should be obvious if I can convince you that this really is so.
>
> Before modern computers came into existence, people made single-purpose computing devices (I am telling you a story, not a history), for example someone made a machine for calculating arctanarctan, and someone else made a machine for calculating the Bessel function. Turing's original insight was that we only had to build one machine (the universal one), which took as input the description of any machine and simulated it. But what is a "description of a machine"? An engineer might think of circuit designs and assembly instructions. But that is very complicated and not easily presented to a machine. And perhaps ever more complicated machines require ever more complicated descriptions?
>
> We need a way of describing machines that is as simple as possible. Here Gödel's idea was important: he showed some years before Turing that all sorts of things in logic (formulas, proofs) could be encoded with numbers, and then manipulated within arithmetic. We can do a similar trick with Turing machines: encode the program, the current state, and the contents of the tape used so far, with a string of symbols on a tape (for examples 00's and 11's), and then manipulate the string with a Turing machine.

We see [here the following explanation of Church-encoding](https://en.wikipedia.org/wiki/Church_encoding):

> In mathematics, Church encoding is a means of representing data and operators in the lambda calculus. The data and operators form a mathematical structure which is embedded in the lambda calculus. The Church numerals are a representation of the natural numbers using lambda notation. The method is named for Alonzo Church, who first encoded data in the lambda calculus this way.
>
> Terms that are usually considered primitive in other notations (such as integers, booleans, pairs, lists, and tagged unions) are mapped to higher-order functions under Church encoding. The Church-Turing thesis asserts that any computable operator (and its operands) can be represented under Church encoding. In the untyped lambda calculus the only primitive data type is the function.

[This statement appears](https://stackoverflow.com/a/18403442/15441) to combine to two in a way that says they're orthogonal (ie that being church-encoded or not is irrelevant to the Gödelization process) - but I'm not sure:

> So let's say that you have natural numbers (or a Church encoding of natural numbers) in your typed lambda calculus. It's possible to do a Gödel numbering that assigns every term in System F to a unique natural number.

My question is: **Can we say that Church encoding is a form of Gödelization?**

**Tags:** functional-programming, compilers, encoding, church-turing-thesis

> **Comments:**
> **username_1**: Is there a scientific question here? It seems awfully vague to ask this question. For instance, why would "Yes we can" be an insufficient answer?  
> **username_0**: Perhaps with an illustration of why you can and a pointer to further reading. Some reasoning would be good too. Perhaps even pointing out flaws in the authors understanding might help.  
> **username_1**: Well, in that case this question should be asked at cs.stackexchange.com. There's nothing research-level about it.  

---

## 1 answers

### Answer by username_2 on 2016-04-02. Score: 1 | Accepted answer

> It's possible to do a Gödel numbering that assigns every term in System F to a unique natural number?

The answer is yes, pick your favorite way of coding terms in F, simply because they are countable number of expressions.

Just being able to assign numbers to expressions in a system is not useful by itself, the question is can it be done in a manner that supports some operations, e.g. substitution, inside the system. The answer is again yes, the standard one works, operations are computable in Girard's F.

> Can we say that Church encoding is a form of Gödelization?

Church encoding is an encoding of *natural numbers* by lambda terms, it is not an *arithmetization of a language* (the correct terminology is arithmetization not Godelization). For arithmetization of a language we need some way of representing natural numbers in a language, but that is independent of the arithmetization of the language itself.

But really the more important question is why would one want to arithmetize a language? Godel does it to be able to talk about the language itself in arithmetic and perform computation over the language. If you think about it what we really want is to talk about computation of functions over the syntactic expressions of a language, and we arithmetize because arithmetic can only talk about numbers. It is just a way of representing language expressions as numbers so we can talk about computation over them, the same way we encode language, numbers, graphs, etc. as binary strings when we deal with computers. Arithmetization was ingenious at the time of Godel, but now it is kind of trivial (in a sense) for a computer programmer. We can encode a formal language as numbers and perform computation over it, sure.

Finally, if you can arithmetize language in a system, you can arithmetize langauge in any system extending it. The syntactic constructions that one is interested do not change from say PA to Godel's T to Girard's F.


---

