![Sample our Computer Science journals, sign in here to start your access, latest two full volumes FREE to you for 14 days]({"type":"image" , "src" : "/sda/5928/TOC-Subject-Sample-2021-Computer-Science.jpg"})
Abstract
The usual methods for associating natural numbers to syntactical objects (Gödel's coding based on prime numbers, codings via pairing functions or by enumerations) are either very complex or produce very high numbers, due to the fact that the numbering is with gaps.
In this paper we propose a method for obtaining good Gödel numberings which is based on the grammatical structure of the language to be coded.
The arithmetization is directed by a top-down parsing algorithm and it works only for context-free unambiguous grammars. It is proved that the coding function such obtained is a bijection between language and natural numbers and its computational complexity is lower than that of the enumerative coding. As an example, Cantor's pairing function is derived. Finally, it is shown how to apply the algorithm for obtaining good Gödel numberings for languages associated to first-order theories.