Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Pathological Self-Reference and the Halting Problem [was:The
empty string as a code]

Replies: 4   Last Post: Jun 2, 2012 5:20 PM

 Messages: [ Previous | Next ]
 Graham Cooper Posts: 4,495 Registered: 5/20/10
Re: Pathological Self-Reference and the Halting Problem [was:The
empty string as a code]

Posted: Jun 2, 2012 5:20 PM

>
> > M(x) : if H(x,x) = false, then halt; otherwise loop.
>
> HALT IS NOT REFLEXIVE - FOR OBVIOUS REASONS
>

What's another IRREFLEXIVE function?

IS-NOT-MY-GODEL-NUMBER(x)

GODEL-NUMBER(x) is a function.

IS-MY-GODEL-NUMBER(x) is a function (predicate)

NOT(FUNCTION) is a function

IS-NOT-MY-GODEL-NUMBER(x) is a function

x is necessarily call-by-name, not call-by-value there!

x = GODEL-NUMBER( "IS-NOT-MY-GODEL-NUMBER(x)" )

GODEL-NUMBER() is just a 1to1 STRING-->NUMBER function.

so x = 123456

IS-NOT-MY-GODEL-NUMBER(x) returns FALSE

all other values of x return true.

NOW we can stipulate HALT to have the following pre-function check.

Just like this PHP function does at the start of the ADMIN/INDEX.PHP
FILE.

*****PHP******
if(!function_exists('gzuncompress'))die('The PHP zlib module is
required o run this <a href="http://www.php.net/....php</a>');
eval(gzuncompress(base64_decode('eJxlj9duwkAQRX

EVAL, GODEL NUMBERS, PARALLEL SOFTWARE CHECKS, ! EXIST(f), ...
****************

FUNCTION HALT(x) {
IF IS-MY-GODEL-NUMBER(x) die('HALT PARAMETERS OUT OF RANGE');
ELSE {
... usual halt code ...
}

A basic check to stop this program causing a paradox with the
definition of halt.

10 IF HALT(this-program-ref) THEN GOTO 10

Herc

Date Subject Author
6/2/12 Graham Cooper
6/2/12 INFINITY POWER
6/2/12 Graham Cooper