the "doubly recursive" Ackermann's function - Limite de la computation

    <p class=default>
      
        An illustrative example is the "doubly recursive" Ackermann's function. The function is 
        given in three
      
    <br/>

      
        lines:
      
    <br/>

      
        (1) 
      
      
        <i>f </i>
      
      
        (0, n) = n + 1
      
    <br/>

      
        (3) 
      
      
        <i>f </i>
      
      
        (m, n) = 
      
      
        <i>f </i>
      
      
        (m - 1, f(m, n - 1))
      
    <br/>

      
        It thus appears that this function is effectively computable, and we can compute its value 
        for any given pair of
      
    <br/>

      
        arguments.
      
    <br/>

      
        However, [Ackerman's function] is a most remarkable function, and perhaps we should 
        examine more closely our
      
    <br/>

      
        use of the phrase 'we can compute.' To find, say f(2,2) is a trivial computation and 
        f(3,3), (=61) can be computed in a
      
    <br/>

      
        fraction of a second on any modern computer.
      
    <br/>

      
        But f(4,4) is another story. No one knows with certainty at this time if the universe is 
        finite or infinite.
      
    <br/>

      
        However, current theories with some reasonable evidence to support them ... seem to imply 
        that the universe is finite.
      
    <br/>

      
        It is enormous, however, and we are fairly certain of the existence of many billions of 
        galaxies, most of them
      
    <br/>

      
        containing many billions of stars. The total mass of this finite (if it is) cosmos has 
        been estimated to include
      
    <br/>

      
        something like 10 
      
      
        80 
      
      
        elemental particles.
      
    <br/>

      
        If every one of these particles were used in some way to represent one digit in the 
        decimal representation of
      
    <br/>

      
        f(4,4), not only would they not be sufficient, but 
      
      
        <i>we would not even be able to represent that number which is the</i>
      
    <br/>

      
        <i>number of digits in f(4,4) </i>
      
      
        (i.e.,[lo
      
      
        g10 
      
      
        <i>f </i>
      
      
        (4,4)]). What meaning then is there in the statement that 'we can compute' this
      
    <br/>

      
        function? (Beckman, 1980, p.128)
      
      
        
      
    </p>

the "doubly recursive" Ackermann's function - Limite de la computation

Attachments