Re: The proof that I was referring to is on the website

From: Arthur J. O'Dwyer (ajo_at_nospam.andrew.cmu.edu)
Date: 08/06/04 

Date: Fri, 6 Aug 2004 13:21:58 -0400 (EDT)

On Fri, 6 Aug 2004, Owen Jacobson wrote:
>> In sci.logic, Marc Goodman wrote:
>>> void LIH(void) { while(Halt(LIH)); }
>>>
>>> int main(int argc, char **argv) { Halt(LIH); return 0; }
>
> Depending on what Halt(M, w) hypothetically does, on a "real" platform,
> it could simply accept a pointer to a function and a pointer to the
> parameters to the function, go dig that function out of memory, and start
> analyzing the machine code (which is an encoding) until it gets to a RET
> or IRET or equivalent.

   True, but that doesn't help anyone solve the Halting Problem.
(Consider what happens to your proposed "solver" if it simply never
encounters a "RET or IRET or equivalent.") And you can't use a
"real" platform to mimic a Turing machine, anyhoo, because a Turing
machine has an infinite tape and a "real" platform presumably does
not. (This rules out the "look for repetitions in state" strategy
which I'm sure you were about to mention.)

-Arthur,
not now you frogk, I'm vatching coorkies

Relevant Pages

  • Re: The proof that I was referring to is on the website
    ... > it could simply accept a pointer to a function and a pointer to the ... > or IRET or equivalent. ... "real" platform to mimic a Turing machine, anyhoo, because a Turing ...
    (comp.theory)
  • Re: Additional resources to understand C better.
    ... Knowledge of assembly language is required for an in depth ... but a char* or void* pointer has a 3-bit offset ... A char* pointer value with a non-zero offset field is a C ... that stuff will differ from platform to platform. ...
    (comp.lang.c)
  • Re: Plz explain me the following code
    ... If the host platform "places" those restrictions, ... actually dereference a NULL pointer. ... Does a compiler that generates such code satisfy the "restrictions ...
    (comp.lang.c)
  • Re: dynamic, static array -> sizeof()
    ... If the OP uses a GNU based platform and for some versions of the ... at all if it's not a dynamically allocated array) but only how ... The OP said he had a pointer returned by malloc, ...
    (comp.lang.c)
  • Re: printf() and void *
    ... Well, no pointer value can be printed portably, since the output ... Right - the technique is portable, ... reasons I like C is because it has portable I/O libraries. ... is no reason to conditionally compile based on the platform the code ...
    (comp.lang.c)