Re: functions that halt

From: |-|erc (contactvia_at_wwwadamskingdom.com)
Date: 04/10/04 

Date: Sat, 10 Apr 2004 22:23:28 +1000

 \ oo
   \____|\mn
    / /_/ /\ \_\
  / K-9/ \/_/ - Found It! -
/____/_____\
--------------

"Patrick Powers" <frisbieinstein@yahoo.com> wrote in
> > There was a post in sci.math last year about the class of functions
> > that are constructed upwards and are guaranteed to halt.
> >
> What does "constucted upward" mean? A sci.math google search doesn't
> find it.
>
> > But what if we assume all programs halt? This doesn't contradict the halting proof,
> > merely denies its construction since it depends on an infinite loop being programmed.
> >
>
> Do you mean, "What if we restrict the class of programs to those
> guaranteed to halt?"

I think this means the same thing, but that would be tedious to find proofs
of standard algorithms, the construction technique would be to make transformations
to build up programs, each transformation is guaranteed not to make a program
fail to halt. Like the iconic menu driven systems now generate "bullet proof" code,
especially for websites.

Herc

All messages from thread
Message 1 in thread
From: Rex Butler (RexButler@hotmail.com)
Subject: Class of computable functions
View this article only
Newsgroups: sci.logic, comp.theory, sci.math
Date: 2003-10-06 17:52:14 PST

I took a class in basic foundations and computability last year, but
there is a question that has been bothering me.

Suppose I want a 'large' computably enumerable collection of functions
f_i : N --> N with the following properties:
1. Each primitive recursive function is included.
2. Each f_i is total by construction.
3. Given i and n in N, there is a computable function time: N x N -->
N which tells me that the value of f_i(n) will take at most time(i,n)
to compute by a turing machine or equivalent.
['Take as long as you want, but PLEASE tell me when you will be
done!']
4. The function time is computable in 'Ackermann + constant' time,
or at least it's behavior is boundedly nasty in some sense. :)

I feel rather queasy about the prospects for this, but it has been
bothering me for too long. The basic theme is this: I want to know
worst case scenario computation time. Will I not get much besides
primitive recursive functions?

Rex Butler

PS I've heard the term 'strongly computable.' Is this related?

Message 2 in thread
From: |-|erc (usemyonlineform@wwwadamskingdom.com)
Subject: Re: Class of computable functions
View this article only
Newsgroups: sci.logic, comp.theory, sci.math
Date: 2003-10-06 21:55:04 PST

"Rex Butler" <RexButler@hotmail.com> wrote in ...
> I took a class in basic foundations and computability last year, but
> there is a question that has been bothering me.
>
> Suppose I want a 'large' computably enumerable collection of functions
> f_i : N --> N with the following properties:
> 1. Each primitive recursive function is included.
> 2. Each f_i is total by construction.
> 3. Given i and n in N, there is a computable function time: N x N -->
> N which tells me that the value of f_i(n) will take at most time(i,n)
> to compute by a turing machine or equivalent.
> ['Take as long as you want, but PLEASE tell me when you will be
> done!']
> 4. The function time is computable in 'Ackermann + constant' time,
> or at least it's behavior is boundedly nasty in some sense. :)
>
> I feel rather queasy about the prospects for this, but it has been
> bothering me for too long. The basic theme is this: I want to know
> worst case scenario computation time. Will I not get much besides
> primitive recursive functions?
>
> Rex Butler
>
> PS I've heard the term 'strongly computable.' Is this related?

take a look at http://members.ozemail.com.au/~chess3/tm1.html

Its 10 lines of code (actually a 5 state Turing Machine) and there is no
proof if it terminates. Only 10 lines and no value for f_i.

In theory your class could be all well defined and well behaved functions,
but in practice they will only be trivial.

Say you are nesting loops, then the invariants at each level would have to
be combined into parallel equations, you have to solve all enumerations
of possible equations, and show they are satisfied for each loop to terminate.

Even then the class of functions has no scope, here is a tiny 3 state TM
http://members.ozemail.com.au/~chess3/tm2.html you can construct it easy
enough but how do you categorise what function it is? ~ binary counter.

Herc

Message 3 in thread
From: H. Enderton (hbe@sonia.math.ucla.edu)
Subject: Re: Class of computable functions
View this article only
Newsgroups: sci.logic, comp.theory, sci.math
Date: 2003-10-07 16:14:34 PST

Rex Butler <RexButler@hotmail.com> wrote:
>Suppose I want a 'large' computably enumerable collection of functions
>f_i : N --> N with the following properties:
>1. Each primitive recursive function is included.
>2. Each f_i is total by construction.
>3. Given i and n in N, there is a computable function time: N x N -->
>N which tells me that the value of f_i(n) will take at most time(i,n)
>to compute by a turing machine or equivalent.
>['Take as long as you want, but PLEASE tell me when you will be
>done!']
>4. The function time is computable in 'Ackermann + constant' time,
>or at least it's behavior is boundedly nasty in some sense. :)

There was a paper 40 years ago somewhat along these lines. If
you want to be able to predict how long a computation will take,
then you have severely restricted the class of functions. Here
is the reference:
    Robert W. Ritchie
    Classes of predictably computable functions
    Transactions of the American Mathematical Society,
    vol. 106 (1963), pp. 139-173
It might help.

--Herb Enderton

Relevant Pages