From: John K Clark (johnkclark@fastmail.fm)
Date: Mon Oct 12 2009 - 21:26:16 MDT
On Mon, 12 Oct 2009 23:16:18 +0100, "Mu In Taiwan"
> The halting problem is not what you think it is. As far as I am aware,
> is quite possible to show that *some* algorithms will or will not halt
No shit Sherlock, if it were not true *all* algorithms would be useless.
What Turing proved is that in general there is no way to prove that any
given algorithm will halt. He proved there are an infinite number of
such algorithms and every one of them is like a tumor to the mind of a
fixed goal AI.
John K Clark
by
> static analysis. It is not possible to show that for *all* algorithms. A
> quick example; here is pseudo-code for an algorithm that is capable of
> detecting a simple infinite loop and not running the code. It has the
> form
> of a regular expression with ? as a wildcard representing i, n, or
> whatever.
> It works for a tiny subset of all possible algorithms, specifically, 1
> line
> for statements with empty bodies.
>
> if sourcecode.string.compare("for (?=0; ?>=0; ?++) { }"); then
> infinite.loop.detected=1; fi
>
> By restricting the contents of the braces to be code known to execute in
> finite time (e.g. single step op-codes, no loops, no recursion, etc), and
> prohibiting the use of whichever variable is represented by "?" while
> inside
> the braces, you could also carry out this test on a larger subset of all
> possible algorithms.
>
> Mu
>
>
>
> On Mon, Oct 12, 2009 at 10:47 PM, Pavitra
> <celestialcognition@gmail.com>wrote:
>
> > JKC, by "fixed goal mind" do you mean "deterministic algorithm", or do
> > you mean something different?
> >
> > If something different, would you please provide an example of either a
> > deterministic algorithm that is not a fixed goal mind, or else a fixed
> > goal mind that is not a deterministic algorithm?
> >
> > I suspect that this would greatly clarify a lot of things.
> >
> > Thank you.
> >
> >
> > Pavitra
> >
> >
-- John K Clark johnkclark@fastmail.fm -- http://www.fastmail.fm - Or how I learned to stop worrying and love email again
This archive was generated by hypermail 2.1.5 : Wed Jul 17 2013 - 04:01:04 MDT