tailieunhanh - ALGORITHMIC INFORMATION THEORY - CHAPTER 2

Part I Formalisms for Computation: Register Machines, Exponential Diophantine Equations, & Pure LISP 19 21 In Part I of this monograph, we do the bulk of the preparatory work that enables us in Part II to exhibit an exponential diophantine equation that encodes the successive bits of the halting probability . In Chapter 2 we present a method for compiling register machine programs into exponential diophantine equations. In Chapter 3 we present a stripped-down version of pure LISP. And in Chapter 4 we present a register machine interpreter for this LISP, and then compile it into a diophantine equation. The resulting equation,. | Part I Formalisms for Computation Register Machines Exponential Diophantine Equations Pure LISP 19 21 In Part I of this monograph we do the bulk of the preparatory work that enables US in Part II to exhibit an exponential diophantine equation that encodes the successive bits of the halting probability Q. In Chapter 2 we present a method for compiling register machine programs into exponential diophantine equations. In Chapter 3 we present a stripped-down version of pure LISP. And in Chapter 4 we present a register machine interpreter for this LISP and then compile it into a diophantine equation. The resulting equation which unfortunately is too large to exhibit here in its entirety has a solution and only one if the binary representation of a LISP expression that halts . that has a value is substituted for a distinguished variable in it. It has no solution if the number substituted is the binary representation of a LISP expression without a value. Having dealt with programming issues we can then proceed in Part II to theoretical .