Machine Learning Ontology Clojure Python Digital Transformation Artificial Intelligence Probabilistic Generative Model Natural Language Processing Deep Learning Mathematics Navigation of this blog
Formal Languages and Mathematical Logics
The programming language I mentioned earlier is a kind of language called a formal language. A formal language is a set of strings (words) that can be generated from a set of base symbols (alphabet, etc.) and generation rules (grammar), and is theoretically based on mathematics called mathematical logic.
Mathematical logic is the foundation of mathematics, and is the study of defining and proving all kinds of things in mathematics using set theory and proof theory. One of the most famous examples is the proof of classical mathematical systems using the ZFC axiomatic system. Roughly speaking, what is done here is to define the basic parts and combine them to construct a large world.
When this is applied to the world of languages, a set of symbols and generation rules (grammar) are defined to generate strings (words). For example, in the LISP language, in the classic “onLISP” by Paul Graham, who is also famous for founding Y Combinator, it is stated that all the remaining functions (programming language in LISP) can be built based on a few functions (words). The language has the ability to generate structure.
A language has a “syntax” to generate structure and a “semantics” to evaluate meaning. The aforementioned example is mainly about the “syntax” that forms the language. The latter, “semantics,” is considered in the study of “semantics,” and semantics in mathematical logic is discussed based on the definition that a proposition (what it says) is meaningful if it is true.
There is a gap between the image of “whether something is true or not” in semantics and the image that the word “meaning” has in the real world, and I felt uncomfortable for a while. In fact, if you look up the word “meaningful” in the dictionary, you will find that it means “it is beneficial to do something,” “something has importance,” or “there is a certain value in doing it,” which is different from the meaning of “whether it is true or not” in mathematical logic. Although the two are not exactly the same thing, we can say that the latter is a precondition for the former between “useful”, “important”, and “valuable” and “it is true”, and this has helped to settle some of the haze of the image gap.
As a reference book on semantics in programming, there is “Program Semantics” by Hirofumi Yokouchi. The table of contents is as follows: Chapter 1: The Concept of Representational Semantics, Chapter 2: Fundamentals of Lambda Calculus, Chapter 3: Fundamentals of Domain Theory, Chapter 4: Semantics of Functional Languages, Chapter 5: Fundamentals of Category Theory, Chapter 6: Domain Equations, Chapter 7: Semantics of Lambda Calculus. It is a bit old book, but you can learn the basics of theories that appear in other LISP books such as lambda calculus and category theory.
For a more in-depth introduction to semantics, I also recommend “Introduction to Modern Semantics” by Kei Yoshimoto and Hiroaki Nakamura. The table of contents is as follows: Chapter 1: Introduction, Chapter 2: Toolbox of Semantics: Sets and Functions, Chapter 3: Propositional Logic, Chapter 4: Predicate Logic, Chapter 5: Phrase Structure Grammar, Category Grammar and Type Theory, Chapter 6: Interior Logic and Possible World Semantics, Chapter 7: Montague Semantics, Chapter 8: Dynamic Semantics, and Chapter 9: Conclusion. The book covers the basics of mathematical logic, possible world semantics, which is the semantics of aspectual logic that logician Saul Kripki came up with when he was in high school, and dynamic semantics, which is a recent theory.
Kripki’s idea that we can think in terms of various possible worlds, rather than a world with only true and false, helped me to bridge the gap between the “meaning” of mathematical logic and the “meaning” of the real world.
For more information on these logics, please refer to “Making Logic Part 1: Beginning Logic Reading Memorandum“, etc. For more information on mathematical foundations, please refer to “Overview of Set Theory and Reference Books“, set theory, or algebra as described in “Structures, Algorithms, and Functions“, etc. Structure, Algorithms, and Functions” for mathematical foundations.
The reason why I have chosen to program using Clojure, which I introduced before, is partly because LISP is a language that has the backing of these mathematical theories. When I think about automatic program generation, which is one of the goals of artificial intelligence, I can imagine how to achieve the “syntax” approach by using LISP, but I have yet to fully imagine the “semantics” approach that is closely related to it. I would like to continue thinking about these issues in the future.
Next time, I would like to discuss natural language processing, which is the opposite of formal languages.
コメント