Conference rusure::math

    OK, what are Church's Thesis and the Riemann Hypothesis?

Church's thesis states that all recursive functions are effectively
computable.  The problem with proving it is that we don't have a
good definition of effective computability.  The evidence for it is
that nobody has found a recursive function for which an effective
procedure can't be constructed from minimalization, partial recursion,
and composition.

I'll let somebody who knows about analysis and number theory define
Riemann's hypothesis.

    I would say that .2 has it backwards.  To say that something is
    "effectively computable" is a little vague.  So various attempts to
    formalize it have been made.  These attempts take something that is
    usually very simple and so would "obviously" be included in anyones
    definition of "effectively computable."  For example, the individual 
    steps that a Turing machine takes are so simple that the Turing
    computable functions must be considered to be "effectively computable."
    
    Almost every such system that has been put forth computes the same
    set of functions that Turing machines can compute, often called the
    general recursive functions.  So Church's thesis states that this is
    what we mean by that vague phrase "effectively computable," that there
    are no other functions that we or our brains or our machines, etc.,
    can compute.  No one has proposed anything outside this set of
    functions that would be generally agreed to be "effectively computable."
    
    Dan
    
    P.S.  Some formal schemes of designing computable functions only
    end up with the primitive recursive functions, a proper subset of
    the general recursive [often simply called "recursive"] functions.

Dan makes some good points in .-1, although I think the observation
about whether it's backwards depends on your training and point of
view.  Church's thesis actually says that the class of recursive
functions and the class of functions for which effective procedures
can be constructed are the same class.

What I was getting at is that the definition of "effectiveness" 
is tough to pin down.  One way of clarifying it is to accept Church
and let it go.  Another way of clarifying it is to reason about 
"effectiveness" by defining certain primitive operations as effective
and then defining rules of combination by which more interesting 
effective procedures can be constructed.  My point is that the
second method leads to some useful insights into the nature of
computation, but isn't strong enough to lead to a proof.

Dave

There is one aspect of the base note which I wonder about.  Church's
Thesis is pretty significant in the theory of computation, since it
gives us some definition of the domain of computation.  We beleive it
without proof, though not without evidence.

Is there similar significance to Riemann's hypothesis?  Is this the
statement about the form of all nontrivial zero solutions to the 
Euler-Riemann function used in prime number theory?

Dave

    Sorry not to be supplying the definition of the Riemann hypothesis,
    I just want to thank the two of you for supplying Church's Thesis.
    
    It seems to me that Church's Thesis in modern mathematics is somewhat
    akin to the Greeks a couple thousand years ago, when they had a similar
    thesis about all numbers being rational.  Once we discover a few
    functions that aren't "effectively computable" we'll probably discover
    there are more of them than those that ARE "effectively computable". 

      John

    Riemann's zeta function is defined as:
    
        zeta(s) = the sum from n = 1 to infinity of 1/(n^s)
    
    Here s is a complex number, and so the branch is probably chosen
    so that 1/(n^s) is e^(-s ln n).
    
    The infinite sum given above converges absolutely for all values of
    the complex variable s such that the real part of s is greater than
    one.  However, through the wonders of functions of a complex variable,
    there are other representations that do "converge" [or whatever] for
    other values of s.  zeta(s) is taken to be the value given by any of
    these representations that happen to be defined for your particular
    s.  However, some values, like s = 1 + 0i = 1,  "diverge" in any
    representation of zeta(s). [i = sqrt(-1)]
    
    Amazingly, for some values of s, zeta(s) = 0 (see note 3)!  A lot of
    these zeroes occur for values of s with a real part of 1/2, i.e.,
    for s = 1/2 + it for some (real) t.  I don't have the precise details,
    but my understanding is that Riemann's zeta hypothesis states that
    ALL of the nontrivial zeroes of zeta(s) in the critical region are of
    the form s = 1/2 + it.
    
    What are nontrivial zeroes?  I don't know.  What is the critical
    region?  I think the strip 0 < real part of s < 1 is it or a
    subset of it.  So for all I know Riemann's hypothesis may be that
    all zeroes of zeta(s) are of the form s = 1/2 + it, period.  But
    I am very sure that the way I stated it above is true if the "full"
    statement of Riemann's hypothesis, whatever it is, is true.
    
    Dan

    Re .6
    
>>                                              Once we discover a few
>>    functions that aren't "effectively computable" we'll probably discover
>>    there are more of them than those that ARE "effectively computable". 
    
    There are "uncountably many" functions from the nonnegative integers
    to the nonnegative integers.  If you think f0, f1, f2, ... is a list
    of all of them, then I will present you with g(n) = fn(n) + 1 which
    differs from every one of your list.  This is essentially Cantor's
    "diagonal" argument that a set cannot be equinumerous with its power
    set.  There are only countably many Turing computable functions,
    because you can list them all as TM0, TM1, TM2, ....  So "almost
    every" function is not effectively computable.
    
    Re .0, some other replies
    
    I always thought of Church's thesis more as a definition than as
    something provable.  It is sort of like saying that the "tractable"
    algorithms are those that run in polynomial time.  Even if you think
    that other algorithms should be considered tractable, or that some
    polynomial time algorithms shouldn't be considered tractable; well,
    even then polynomial time algorithms are interesting to study.
    
    So, the Turing computable = Markov computable = general recursive
    functions are a strictly defined set of functions that are very
    interesting and sometimes relevant to study.  It appears that this
    _is_ the class of effectively computable functions.  But even if
    you disagree, and feel that say, luck or divine intervention or
    inspired guessing allow the class of effectively computable functions
    to contain non recursive functions -- well, go ahead, but don't let
    that belief cause you to miss out on studying all this wonderful
    theory!
    
    I guess this isn't very eloquent.  But I see Church's thesis as
    a motivation for studying the precisely defined set of recursive
    functions.  A lot of mathematical "objects" are studied because
    of someone's "hypothesis" that they model some intuitive or "real
    world" subject.  Riemann's hypothesis is a precisely defined statement
    [well, not in .-1] about the complex numbers.  The first isn't
    really subject to proof or disproof; the second is.  
    
    Dan

    re: .8
    				      x
    Are you saying that, say, f(x) = e  is not "effectively computable"?
    
    and is therefore not "very interesting and sometimes relevant to study."

    Is all of this in light of a restricted branch of mathematics? (maybe
    we call it computational complexity or equivalent)
    
    Does the notion of "effectively computable" extend into linear algebra?
    Complex variables?  Real analysis?  Measure theory?  Set theory?
    
      John

>    				       x
>    Are you saying that, say, f(x) = e  is not "effectively computable"?

Yes, because e is transcendental and therefore infinite in length and 
non-repeating. I think you are confusing "Approximately computable" - which
nearly everything is - with "effectively computable", which nearly 
everything isn't, as it implies finiteness.

This touches on an issue that has been discussed in other notes - that 
there is no way of expressing transcendental numbers in a computer except 
as functions of integers; in other words, every number that can be 
expressed in a computer of finite size is an integer of finite length or
is some sort of functional representation with integers as arguments.
Thus Pi, e, etc. are not effectively computable.

RE: .10
    
    >"Approximately computable" - which nearly everything is ...
    
    I'd need a definition for "approximately computable" to say anything
    definite about it, but if it means what it sounds like it means
    then this statement is wrong.  The probability that a randomly chosen
    function is "approximately computable" is zero.  I don't have a
    proof for this, but I am more than reasonably certain that it is
    correct.
    
    Most (infinitely more than not) functions are completely erratic
    -- they are only describable by a (non-linear) "list" associating
    each real (assuming we are talking about functions from the reals
    to the reals) with another real, without any consistent relation
    between between those pairs.  There are only a countably infinite
    (at most) computable functions -- to expect that nearly all functions
    (do I remember that there are more functions R->R than there are
    reals) are such that one of those effectively computable functions
    will have less than a given error for every one of those pairs
    does not make much sense.
    
    					Topher

    Some of the recent replies have ignored replies .2, .3 and .4, which
    explain the problem, misstating the thesis in a form that's trivially
    false.

>    Some of the recent replies have ignored replies .2, .3 and .4, which
>    explain the problem, misstating the thesis in a form that's trivially
>    false.

    Please tell us how .2, .3, and .4 misstate the thesis in a form
    that's trivially false.

Sorry.  Read it as:

    Some of the recent replies have [been] misstating the thesis
    in a form that's trivially false.

     Re .9, .10

     First off, I thought I had said recursive function theory
     was interesting whether or not you believed in Church's
     thesis.  I don't recall saying the exponential function
     wasn't interesting.  Functions over the complex numbers are
     interesting too, although not usually during football games. (-:

     In the earlier replies where I mentioned "Turing computable
     functions" or "general recursive functions" I was referring
     to "n-ary" functions for some finite n with arguments and
     values in the nonnegative integers.  So for instance

                 f(m, n) = m + n     [m,n = 0, 1, 2, 3, ...]

     is a recursive function, but

                           { 1 if Turing machine m with input n halts
                 g(m, n) = {
                           { 0 otherwise

     is not recursive.

     One can talk about "computable" real or complex numbers, but
     you have to define what you mean, just like "Turing
     computable" or "general recursive" have been given strict
     definitions.

     So here is possible definition: a real number is computable
     if and only if there is a two tape Turing machine, limited
     so that cells on the second tape may never be changed after
     the first write to the cell, such that when started with
     blank tapes the machine proceeds to write out the real
     number in binary on the second tape, with the alphabet
     {0,1,.}.  This process will not terminate if the binary
     representation is infinite.

     Or, definition two:  a nonnegative real number x is
     computable if and only if the function over the nonnegative
     integers given by f(n) = [nx] = the greatest integer <= nx
     is Turing computable.

     There are other definitions, for example f(m, n) = 1 iff n
     is not zero and the rational m/n is less than x, f(m, n) = 0
     otherwise.  Under all of these e = 2.71828... is computable.

     In any of these definitions of "computable," there are only
     countably many "programs" and therefore only countably many
     computable reals, although there are uncountably many reals. 
     So almost all reals are not computable.  [:-) but most of
     the "interesting" real numbers are computable (-:]

     One can also talk about functions over the reals being
     computable.  For instance, if a three tape Turing machine is
     started with two blank tapes and the third tape having the
     [potentially] infinite decimal of x on it, and it writes the
     [potentially] infinite decimal for f(x) on one of the
     initially blank tapes , then f is computable.  Notice that
     here f(x) = 3x is not computable; given input x = 1/3 =
     0.333333333... the machine would scan forever, never knowing
     whether to start off with "1." or "0."  Assuming you didn't
     allow 0.99999.... for 1.

     So is e^x computable?  For integral m, f(m, n) = [ne^m] is
     recursive.  A similar statement holds for rationals.  But if
     x is a real such that f(n) = [nx] is recursive, then will
     g(n) = [ne^x] also be recursive?  Could be.  Is h(m, n) =
     [ne^x] for that real number x such that Turing machine m
     computes f(x) = [nx] recursive?  That seems less likely,
     given the previous paragraph.

     So it is possible to speak of computable reals and of
     computable functions over the reals.  I don't know of any
     established definition of what that means, but you can
     define it in a plausible way.

     Dan

Newsgroups: sci.math
Path: decwrl!labrea!agate!pasteur!ames!umd5!cvl!ramesh
Subject: Re: Fermat's Last Theorem apparentl
Posted: 6 Apr 88 00:49:12 GMT
Organization: Center for Automation Research, Univ. of Md.
 
In article <73300024@uiucdcsp> gillies@uiucdcsp.cs.uiuc.edu writes:
>
>Isn't it funny how people complain about believeing The Rieman
>Hypothesis -- whose proof is supposedly within reach -- while assuming
>Church's Thesis holds true -- because it's proof seems beyond our
>reach!  This is so counter-intuitive!
>
>Don Gillies {ihnp4!uiucdcs!gillies} U of Illinois
>            {gillies@p.cs.uiuc.edu}
 
 
There are  crucial differences between Church's hypothesis(CH) and 
the Riemanian conjecture (RC).
 
CH is a non-mathematical statement. It simply connects
the precise definition of computability to some intuitive
notions of computability that we may have. Consequently,
one need not beleive in CH to beleive any result in
recursion theory or any other computational theory. No
proof depends on the truth or falsity (whatever that may
mean for a non-mathematical statement)  of CH.
 
Clearly this is not the case for RC. 
 
				Ramesh
-- 
ARPA:  ramesh@cvl.umd.edu |Why should anyone suppose that all that matters 
SPRINT:(301) 431 0838     |to human nature can be assessed with a measuring
UUCP:  ramesh@cvl.uucp    |rod ? The nature of all reality is spiritual.
                          |            Sir Arthur Eddington

Newsgroups: sci.math
Path: decwrl!labrea!eos!ames!ucsd!sdcsvax!ucsdhub!ucrmath!marek
Subject: Re: Fermat's Last Theorem apparentl
Posted: 5 Apr 88 18:05:04 GMT
Organization: University of California, Riverside
 
In article <73300024@uiucdcsp>, gillies@uiucdcsp.cs.uiuc.edu writes:
> 
> Isn't it funny how people complain about believeing The Rieman
> Hypothesis -- whose proof is supposedly within reach -- while assuming
> Church's Thesis holds true -- because it's proof seems beyond our
> reach!  This is so counter-intuitive!
 
It does not make much sense to compare Rieman's hypothesis with Church's
thesis, because Rieman's hypethesis is a formal statement in formal
mathematical language, while Church's thesis is not. Also, the word "true"
has a different meaning in both cases.
 
If one says that Rieman's hypothesis is true, then he means it can be
*proved*. That is, it can be derived from the axioms of set theory.
Other possible cases are: it's negation can be proved, or that it is
independent of the axioms. In this case "true" means "provable".
 
Church's is not a mathematical statement, so it's not possible to prove
it in the above sense. It's not because "it's proof seems beyond our reach".
It's just does not make sense to talk about it's proof. It says that our
definition of a computing device (Turing's machine) is accurate and exhaustive.
It's like the laws of ecomomics or nature. All we can hope for in this case 
are common-sense arguments fot it's validity. Such arguments exist, and are
fairly easy and convincing. 
 
 Imagine, that one day someone invents a miraculous device which, given a
program in Pascal, can answer whether it halts or not. This would show that
we were wrong. But still, all theorems in complexity theory ARE TRUE, cause
they talk about computability in the formal sense, using the Turing machine
model. It would only show that the model is too weak. 
 
 If one does not believe in Church's thesis, then why not doubt that the
notion of function, number, etc. are properly defined?
 
Marek

Newsgroups: sci.math
Path: decwrl!labrea!agate!pasteur!ames!nrl-cmf!cmcl2!brl-adm!brl-smoke!gwyn
Subject: Re: Fermat's Last Theorem apparentl
Posted: 6 Apr 88 16:10:18 GMT
Organization: Ballistic Research Lab (BRL), APG, MD.
 
In article <176@ucrmath.UUCP> marek@ucrmath.UUCP (Marek Chrobak) writes:
>If one says that Rieman's hypothesis is true, then he means it can be
>*proved*. That is, it can be derived from the axioms of set theory.
>Other possible cases are: it's negation can be proved, or that it is
>independent of the axioms. In this case "true" means "provable".
 
I have to take exception to this.  I am pretty sure the RH is true,
but I doubt very much that it will ever be proved, given that it
hasn't been by now.  In any case a growing portion of mathematics
is not based on set theory, but that doesn't make it less valid or
"proven"; quite the contrary.  It wouldn't at all surprise me if it
turned out that the RH was not deducible in any real sense from a
self-consistent formulation of conventional set theory; yet it is
not "independent" in the sense that the axiom of choice is, for
example.  Remember Goedel's result that there are true unprovable
theorems in number theory.  For all we know, RH may be one of them.

Newsgroups: sci.math
Path: decwrl!labrea!kestrel!ladkin
Subject: Re: Fermat's Last Theorem apparentl
Posted: 6 Apr 88 21:18:06 GMT
Organization: Kestrel Institute, Palo Alto, CA
 
In article <176@ucrmath.UUCP>, marek@ucrmath.UUCP (Marek Chrobak) writes:
> If one says that Rieman's hypothesis is true, then he means it can be
> *proved*. That is, it can be derived from the axioms of set theory.
> Other possible cases are: it's negation can be proved, or that it is
> independent of the axioms. In this case "true" means "provable".
 
It's perfectly legitimate to say that there are true but unprovable
statements of set theory. The consistency of set theory (meaning ZF)
would be one of them. So I would not accept your equation of `true'
with `provable from ZF'. 
 
peter ladkin
ladkin@kestrel.arpa

	
    To clear up some confusion, Church's Thesis states:

               Every calculable function or predicate is recursive.
    
    There is an obvious difficulty in proving Church's Thesis in that we
    have no precise definition of calculable. This is not necessarily an
    insuperable difficulty. The converse of Church's Thesis that:
    
    	       Every recursive function or predicate is calculable.
    
    HAS been proved.       

    Marc.

    Re : .10 Thus Pi, e etc. are not effectively computable.
    
    Hold on a minute is this right? I not too sure what you mean by  
    effectively and approximately computable. However Pi and e are recursive
    real numbers. Note not all real numbers are recursive but Pi and e are.
    
    Marc.

    Hang on a moment to clear up the confusion:
    
    Question (Assuming Church's Thesis)
    
    Do your ideas of effectively computable and approximately computable
    correspond to the mathematical ideas of:
    
    a) Recursive & Primitive Recursive Functions. OR
    
    b) Recursively Enumerable and Recursive Fuctions?
    
    The set of PRIMITIVE RECURSIVE functions includes the basic fuctions and 
    is closed under substitution (composition) and recursion.
    
    The set of RECURSIVE functions includes the basic fuctions and 
    is closed under substitution (composition) and minimalisation. This
    includes the set of recursive functions.
    
    Marc.