Re: A modern view of the halting problem

Alex McDonald wrote:
T.M. Sommers wrote:
Alex McDonald wrote:
T.M. Sommers wrote:
Frank Kotler wrote:
Herbert Kleebauer wrote:

A closed, finite digital system can by definition only be in one of N
different states. To decide whether a program halts or not, you
only have to execute it N clock cycles, either it halts within this time
or it never will halt.

Hmmm... Can we guarantee to hit all N states in N clock cycles? Doesn't
"seem right" to me, but I don't know much about it.

If you assume:

1) no input or other external influences (so the user doesn't say
no N+1 times when asked if he wants to quit); and
2) the next state depends solely on the current state (which
really includes #1); and
3) one state change per clock and one clock per state change,

then if you have not hit all N states in N clocks you must have
hit one state twice, which implies a loop that will endlessly repeat.

The method is not practical, except for trivially small N.

Who said anything about practical? I was just trying to point
out the underlying assumptions of the claim, with the expectation
that the impracticality would be then be even more obvious.

My apologies. I find it is safest to assume nothing on ala.

No apology necessary. No offense was taken. Although it maybe didn't sound like that.

--
Thomas M. Sommers -- tms@xxxxxx -- AB2SB

.

Relevant Pages

  • Re: A modern view of the halting problem
    ... To decide whether a program halts or not, ... only have to execute it N clock cycles, either it halts within this time ... hit one state twice, which implies a loop that will endlessly repeat. ... It should be pointed out that the bits in question are not must main memory, but every bit in the machine, including registers, flags, caches, buffers, disks, etc. ...
    (alt.lang.asm)
  • Re: A modern view of the halting problem
    ... To decide whether a program halts or not, ... Can we guarantee to hit all N states in N clock cycles? ...
    (alt.lang.asm)
  • Re: A modern view of the halting problem
    ... To decide whether a program halts or not, ... Can we guarantee to hit all N states in N clock cycles? ...
    (alt.lang.asm)
  • Re: A modern view of the halting problem
    ... To decide whether a program halts or not, ... Can we guarantee to hit all N states in N clock cycles? ...
    (alt.lang.asm)
  • Re: Principle of equivalence
    ... what the Lorentz equations say with regard to where a clock thrown ... from a moving frame of reference will hit just by saying it was thrown ... from the frame of reference. ...
    (sci.physics.relativity)