Re: Solution to the halting Problem?

From: Owen Jacobson (angstrom_at_lionsanctuary.net)
Date: 07/24/04 

Date: Sat, 24 Jul 2004 20:25:44 GMT

On Sat, 24 Jul 2004 13:10:48 +0000, Peter Olcott wrote:

>> Recall that all computers[0] can simulate all other computers, as well.
>> So, while your algorithm may be writing to 'the screen' using 'protected
>> memory', it may be operating in a simulated environment where those two
>> operations are implemented by simply storing the displayed information for
>> later retrieval. This does not change your algoritm one iota: a
>> simulation has *at least* the same characteristics and capabilities of the
>> original. This simulation could be on any equally-powerful computer.

This is still an important point. No algorithm can determine whether it's
running on a computing machine or a simulation of a computing machine, and
a simulated computing machine can perform extra operations based on the
simulated algorithm without disturbing its operation.

>> (Below I refer to the compound noun 'subjects'; I mean the subject
>> algorithm M combined with the subject input x.)
>>
>> Any algorithm that can tell a hypothetical user/observer if the subject
>> algorithm with the subject input will halt must, by definition, at some
>> point during its execution contain information about whether the
>> subjects halt or not. Agreed?
>
> YES.
>
>> If it contains that information, it *is* *always* possible to write the
>> exact same algorithm to the point where that information is present, and
>> then deviate. Up until the point where they deviate, they are the same
>> algorithm. At the point of deviation, both contain absolute information
>> about whether subjects halt. Agreed?
>
> NO.
> http://home.att.net/~olcott/halting/index.html#objection03

Non-sequitor. You've answered "Do you agree that it must be possible to
return that information to another algorithm?" I'm asking "Do you agree
that it's possible to write other algorithms that, up to the point where
the information about whether the subjects halt exists, are identical?"

Identical means performing the exact same series of operations on the
inputs, starting from the same state. If you examined what the machine
had already done, and what state it was in *at the point where this
information becomes available*, you would not be able to tell which of
yours or some other algorithm you were examining. Agreed?

> I have not solved every definition of the Halting Problem.
> I have only solved the original definition of the Halting Problem.

This is a mathematical question, where these differences in wording have
specific meanings. Be very careful, and *always* choose the right words.
What you actually have is "an attempted refutation of Turing's proof that
no algorithm can determine whether any arbitrary algorithm and its input
will halt." Verbose, but much more accurate. 

-- 
Some say the Wired doesn't have political borders like the real world,
but there are far too many nonsense-spouting anarchists or idiots who
think that pranks are a revolution.

Relevant Pages

  • Re: Humaniform robots... yea or nay?
    ... algorithm does what you think it does. ... at least the course left you with the realization that genetic algorithms/programmings are not to be trifled with if you have a lousy simulation environment/test case. ... I think there's an obvious problem of generalizing this experience to genetic algorithms/programming in general. ... But then, a lot of the things that would at one point have been considered the forefront of AI research are now becoming mainstream: facial recognition software, speech recognition and synthesis, and so on. ...
    (rec.arts.sf.science)
  • Re: Variational calculus : A drop of water
    ... Simulation of a Dripping Faucet by Nobuko Fuchikami, ... By taking a stable equilibrium shape as an initial ... we describe a variational algorithm to examine ... Our algorithm of simulation of dynamics ...
    (sci.math)
  • Re: need a good implementation of pseudorandom generators
    ... use SPSS to generate the random mumbers. ... The Marsaglia algorithm is also available as an option. ... pseudorandom generator for it. ... But if i run the simulation 100 times then on all 100 times it gives ...
    (sci.stat.math)
  • =?utf-8?q?Q(=CE=BB)-learning_algorithm_question?=
    ... For Watkin's Q-learning algorithm; why would someone ... simulation and on real robot show that \lambda=0.5 gives a solution ... [ask your news administrator to fix the problems with your system. ...
    (comp.ai)
  • Re: Release of RosAsm V.2.025a
    ... >> we want an other algorithm HALTwhich tells us, whether ... >> a HALT() which does this for any. ... > The amount of resources has nothing to do with it. ... > disassembler cannot be written that automatically does this, ...
    (alt.lang.asm)
Loading