Re: functions that halt

• Previous message: Kamran Karimi: "Software for causal and acausal rule discovery"
• In reply to: The Ghost In The Machine: "Re: functions that halt"
• Next in thread: Michael Mendelsohn: "Re: functions that halt"
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

Date: Thu, 15 Apr 2004 09:22:28 +1000

 \ oo
   \____|\mn
    / /_/ /\ \_\ - Herc, The Unrecognised Truman
  / K-9/ \/_/ - Join www.chatty.net -
/____/_____\ - Nanotechnology is gonna be HUGE... (RMF)
--------------

"The Ghost In The Machine" <ewill@sirius.athghost7038suus.net> wrote
> >> >>
> >> >> Like all diagonal arguments, this one ASSUMES the existence of something (in
> >> >> this case, some computable total F that enumerates all and only the computable
> >> >> total functions on N->N), and then shows that that leads to a contradiction,
> >> >> thus demonstrating that the assumption was false (in this case, demonstrating
> >> >> that there can be no such F).
> >> >>
> >> >
> >> > WRONG!
> >> >
> >> > I'll call elements of F constructable functions. Now tell us where has anyone
> >> > defined constructable functions to allow calls to other functions?
> >> >
> >> > G = lambda x (.... F x ....)
> >> >
> >> > Constructable functions do not allow all function calls. Doing so would only
> >> > require an additional small set of primitive functions, eg. Succ(), Twice() to make
> > constructable
> >> > functions equivalent to all possible TMs and therefore amenible NOT to halt.
> >> >
> >> > F halts, G calls F, by inspection if F halts then G halts.
> >> > THEREFORE G belongs to the set of halting TMs,
> >> > NOT necessarily to the set of constructible functions.
> >> >
> >> > Constructible functions are a proper subset of halting functions,
> >> > and G is not constructable.
> >> >
> >> > Herc
> >> >
> >>
> >> I for one don't see a problem here. If f() is a primitive recursive
> >> function (I'm assuming this is what you mean by "constructable";
> >> I'm also assuming that a primitive recursive function is a function
> >> that is either totally primitive (e.g., f(x) = x + 1) or a
> >> function that is implemented using fixed-limit for loops
> >> (e.g., f(x) = x! can be implemented using the code
> >>
> >> int p = 1;
> >> for(i = 1; i <= x; i++) p = p * i;
> >> return p;
> >> )
> >>
> >> and g() is a primitive recursive function, then so is their
> >> sum, difference, product, quotient, and composition.
> >>
> >> The only thing not allowed is the general mu-loop:
> >>
> >> while(!done) { ... }
> >>
> >> and function composition doesn't need that.
> >>
> >
> > while (x) {
> > abc
> > }
> >
> > is equivalent to tail recursion :
> >
> > fun w (x) {
> > if (x) {
> > abc
> > w (x)
> > }
> > }
>
> Correct.
>

So...

> >> The only thing not allowed is the general mu-loop:
> >>
> >> while(!done) { ... }
> >>
> >> and function composition doesn't need that.

function naming is not allowed either, because it is equivalent to allowing 'while'.

Actually while (x) is allowed if it can be 'calculated' that the loop terminates.

Examine :

i = 1
while (i < 10) {
   i++
}

Calculate the loop invariant, this is something that does not change throughout
the execution of the loop. Here it is i>0.

Then solve simultaneous equations given the ending condition for the loop and
the loop invariant :

i >= 10
i > 0

This has a solution when i = 10, which demonstrates the loop can terminate.

> >
> > Constructable functions can be defined to remove
> > general function calls. In practice they might be
> > tested if they were safe to call, but in theory named
> > functions are not required for computability at all..
> >
> > You haven't coded until you do nested lamda definitions on the fly.
>
> Guess I haven't coded then. I'm not familiar enough with LISP
> to do that, and in any event my speciality is mostly C++.

In practice humans like to name functions and keep everything modular,
in theory TMs and pure functions are just a single function body.

>
> >
> > You might not see a problem but the diagonalisation proves squat,
> > you assumed the class of halting functions under consideration
> > perform function calls.
>
> You are correct; the diagonalization of a computable list, as it
> turns out, proves absolutely nothing. The reason is that a
> computable list is a list of FINITE algorithms [*]. The diagonal
> is not a finite algorithm.

clarify finite algorithm?

>
> > When you rewrite G in terms of evaluating_indexed_functions (F)
> > and extrapolating those function bodies from their index,
> > guess what? G won't halt. Eventually G will come
> > to its own (prospective) index number and representation,
> > construct its own body and evaluate that. Either G is accepted
> > because it recognises the infinite recursion and outputs null for
> > its own diagonal digit, or G will be recognised by the specifications
> > of constructable functions (part of F) as failing to halt and is not
> > in the set of constructables.
> >
> > The diagonal is not computable by constructable functions.
> > You have yet to prove what limitation the absense of self
> > referencing paradoxical non functions actually is.
>
> There is no limitation. G simply won't halt.
> It will go into an infinite loop 5,4,5,4,5,4... and one can
> wait until doomsday, but it won't halt. Eventually a
> real machine would crash as it runs out of stack space.
>
> Mea culpa. However, I don't see how this proves that the
> set of real numbers is finite and/or denumerable.
>

Does it disprove Barbs diagnonalistion attack on a theory of guaranteed halting functions
being equivalent in power to the class of TMs?

Herc

• Previous message: Kamran Karimi: "Software for causal and acausal rule discovery"
• In reply to: The Ghost In The Machine: "Re: functions that halt"
• Next in thread: Michael Mendelsohn: "Re: functions that halt"
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]