Re: functions that halt

From: Michael Mendelsohn (keine.Werbung.1300_at_msgid.michael.mendelsohn.de)
Date: 04/12/04 

Date: Mon, 12 Apr 2004 05:25:40 +0200

Barb Knox schrieb:
> In article <4079D1D8.4C050005@msgid.michael.mendelsohn.de>,
> Michael Mendelsohn <keine.Werbung.1300@msgid.michael.mendelsohn.de> wrote:
> >> functions you've described seem to be the "primitive-recursive" ones (a.k.a.
> >> Delta^0_0). There are many other total functions not in that set.
> >
> >Are these useful?
>
> Yes indeed.

Could you give me an example, please?

>
> >> To make matters rather more difficult, the entire set of total functions
> >> (say on N->N) can not itself be generated by ANY algorithm (i.e. it is
> >> not "recursively enumerable"). This can be proven by a simple diagonal
> >> argument:
> >> if there were some enumeration function F(i) that returned an encoding of
> >> the i'th total function on N, then define G(j) = 4 if F(j)(j) =5 and
> >> G(j) = 5 otherwise. Since F(j) is a total function then F(j)(j) is total
> >> and thus G(j) is total, but by construction G =/= F(i) for any i; thus
> >> there can be no such F that lists ALL the total functions.
> >
> >Doesn't make it difficult, it makes it easier - you'd have proven that
> >no programming language can describe all total functions, so it doesn't
> >hurt too much if mine can't. :)
>
> Not quite: the proof shows that no programming language can describe ALL and
> ONLY the total functions.

I do not see where your proof is restricted to programming languages.

> Clearly ANY Turing-complete language can describe
> all computable functions; but there's no algorithmic way to tell which ones of
> those functions are total -- that would be similar to solving the halting
> problem.

I think that not all total functions are computable, then.

> >I think another way to prove this would be to define a function
> > g:r->f(r)()
> >with f(r)(i) = i + <ith decimal digit of r>
>
> The problem with that is that you're ASSUMING every real number is computable
> by some algorithm (i.e. you can enumerate its digits). This assumptions is
> false, as can be shown by another diagonal argument.

No, I don't assume that.
My proof doesn't concern computability at all, only the number of total
functions on N, computable or not. Also I do not need to enumerate all
its digits, I merely need to determine the ith deciml digit of r, which
can be quickly accomplished. In other words,
f(r)(i) = i + floor(r * 10^i- floor(r*10^(i-1))*10)

> No, there are a countable number of total functions, because there are a
> countable number of functions altogether: just pick a complete programming
> language and enumerate all syntactically valid programs of length 1 character,
> then 2, then 3, ....

That's circular reasoning: you assume that all total functions on N are
computable - a fact not in evidence. (Or am I being stupid?)
If what you state here is true, all total functions (on N) would be
computable, because there's a syntactically valid Turing Machine program
for all of them (and in fact your enumeration algorithm generates them
all).
Isn't that what you wanted to disprove in the first place?

Trying to wrap my head around
http://www.informatik.fernuni-hagen.de/import/thi1/klaus.weihrauch/book.html
...

Michael 

-- 
Feel the stare of my burning hamster and stop smoking!

Relevant Pages

  • Re: functions that halt
    ... >> there can be no such F that lists ALL the total functions. ... >no programming language can describe all total functions, ... by some algorithm (i.e. you can enumerate its digits). ... >uncountable number of reals in any interval. ...
    (comp.theory)
  • Re: Turing completeness of the functional paradigm?
    ... beyond what is usual for constructive mathematics. ... We can enumerate ... do compute total functions N->N, ...
    (sci.logic)