Andy Melnikov (nponeccop) wrote,
Andy Melnikov

Уравнение, эквивалентное задаче останова

Диофантово уравнение с параметром, решение которого в общем виде эквивалентно задаче останова

Formalisms for Computation: Register Machines, Exponential Diophantine Equations, & Pure LISP

By Gregory. J. Chaitin

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, i.e., 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.
Tags: до чего техника дошла

  • Post a new comment


    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.