tailieunhanh - ALGORITHMIC INFORMATION THEORY - CHAPTER 3

A Version of Pure LISP Trong chương này chúng tôi trình bày \ dãi "simpli ed phiên bản của LISP tinh khiết thiết kế đặc biệt cho các ứng dụng metamathematical Ngoài các quy tắc mà một biểu thức S-phải có cân bằng () 's, cách duy nhất là một biểu thức có thể không có giá trị. vòng lặp mãi mãi Điều này là rất quan trọng bởi vì các thuật toán mô phỏng các thuật toán khác được chọn ngẫu nhiên, phải có khả năng chạy rác một cách an toàn. phiên bản này của LISP phát. | Chapter 3 A Version of Pure LISP Introduction In this chapter we present a permissive simplified version of pure LISP designed especially for metamathematical applications. Aside from the rule that an S-expression must have balanced O s the only way that an expression can fail to have a value is by looping forever. This is important because algorithms that simulate other algorithms chosen at random must be able to run garbage safely. This version of LISP developed from one originally designed for teaching Chaitin 1976a . The language was reduced to its essence and made as easy to learn as possible and was actually used in several university courses. Like APL this version of LISP is so concise that one can write it as fast as one thinks. This LISP is so simple that an interpreter for it can be coded in three hundred and fifty lines of REXX. How to read this chapter This chapter can be quite difficult to understand especially if one has never programmed in LISP before. The correct approach is to read it several times and to try to work through all the examples in detail. Initially the material will seem completely incomprehensible but all of a sudden the pieces will snap together into a coherent whole. Alternatively one can skim Chapters 3 4 and 5 which depend heavily on the details of this LISP and proceed 79 80 CHAPTER 3. A VERSION OF PURE LISP 0 ABCDEFGHIJKLMNOPQRSTUVWXYZ abcdefghijklmnopqrstuvwxyzO123456789 _ -. . 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o Figure The LISP Character Set. These are the 128 characters that are used in LISP S-expressions the left and right parentheses and the 126 one-character atoms. The place that a character appears in this list of all 128 of them is important it defines the binary representation for that character. In this monograph we use two different representations 1 The first binary .