Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]


Groups > comp.theory > #39613

Re: Converting Recursive Definition into Closed Form: The Holy Grail of Algorithmics

From Jeff Barnett <jbb@notatt.com>
Newsgroups comp.theory
Subject Re: Converting Recursive Definition into Closed Form: The Holy Grail of Algorithmics
Date 2021-09-20 11:05 -0600
Organization A noiseless patient Spider
Message-ID <siaf08$1ft$1@dont-email.me> (permalink)
References <a7c2345d-e3ab-4296-8b1b-877212aa8c7dn@googlegroups.com>

Show all headers | View raw


On 9/20/2021 10:38 AM, Charlie-Boo wrote:
> A closed form i.e. O(1) is the Holy Grail of Algorithmics.
> 
> Every problem is a recursive definition since running a program is evaluating a recursive definition.
> 
> [Let INIT = Initial State.  NEXTSTATE(state) = Iterate.  HALTS(state)="Does state halt?" Then PROG(Input) is HALTS(Input)?Input:PROG(NEXTSTATE(Input)).]
> 
> The Nth Fibonacci Number is a recursive definition but there is a closed form (e.g. wiki.)
> 
> (The trick, however, is that iteration is replaced by exponentiation of a real number.)
> 
> How far have people gotten in developing closed forms for recursive definitions starting with Fibonacci?
> 
> Solving this 2-place function over N would be helpful (I will explain.)
> 
> 2	5	34	1,597
>   	8	55	2,584
> 	  	144	6,765
> 	  	 	46,368
> 
> C-B
> 

First things first. Evaluating a closed form is not necessarily O(1). 
For example, 2^{2^{2^ ...... {2^n}}} is as much a closed form as is n^2. 
If we are measuring computational cost, there is a non constant amount 
of work to do depending on the size of n, the representation of n, and 
the representation of the value. Further, the order of magnitude of the 
work depends on algorithm and computing device.

I think what you meant to say is evaluating f(n) is O(1) if f(x) is a 
constant for all x. Of course if your computation method must read x 
even though it is not relevant, than the order of the work is O(|x|), 
where |x| is the length of the string representing the value of x.
-- 
Jeff Barnett

Back to comp.theory | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread


Thread

Converting Recursive Definition into Closed Form: The Holy Grail of Algorithmics Charlie-Boo <shymathguy@gmail.com> - 2021-09-20 09:38 -0700
  Re: Converting Recursive Definition into Closed Form: The Holy Grail of Algorithmics Jeff Barnett <jbb@notatt.com> - 2021-09-20 11:05 -0600
    Re: Converting Recursive Definition into Closed Form: The Holy Grail of Algorithmics Charlie-Boo <shymathguy@gmail.com> - 2021-09-20 11:43 -0700
      Re: Converting Recursive Definition into Closed Form: The Holy Grail of Algorithmics Jeff Barnett <jbb@notatt.com> - 2021-09-20 14:01 -0600
        Re: Converting Recursive Definition into Closed Form: The Holy Grail of Algorithmics Charlie-Boo <shymathguy@gmail.com> - 2021-09-24 16:41 -0700
          Re: Converting Recursive Definition into Closed Form: The Holy Grail of Algorithmics Jeff Barnett <jbb@notatt.com> - 2021-09-24 20:46 -0600
  Re: Converting Recursive Definition into Closed Form: The Holy Grail of Algorithmics Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-09-20 21:38 +0100
    Re: Converting Recursive Definition into Closed Form: The Holy Grail of Algorithmics Charlie-Boo <shymathguy@gmail.com> - 2021-09-24 11:10 -0700
    Re: Converting Recursive Definition into Closed Form: The Holy Grail of Algorithmics Charlie-Boo <shymathguy@gmail.com> - 2021-09-24 11:23 -0700
      Re: Converting Recursive Definition into Closed Form: The Holy Grail of Algorithmics Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-09-24 21:40 +0100
    Re: Converting Recursive Definition into Closed Form: The Holy Grail of Algorithmics Charlie-Boo <shymathguy@gmail.com> - 2021-09-24 16:45 -0700
      Re: Converting Recursive Definition into Closed Form: The Holy Grail of Algorithmics Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-09-25 21:31 +0100
        Re: Converting Recursive Definition into Closed Form: The Holy Grail of Algorithmics Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2021-09-26 10:26 -0700
          Re: Converting Recursive Definition into Closed Form: The Holy Grail of Algorithmics Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-09-26 19:02 +0100
    Re: Converting Recursive Definition into Closed Form: The Holy Grail of Algorithmics Charlie-Boo <shymathguy@gmail.com> - 2021-09-24 17:04 -0700
      Re: Converting Recursive Definition into Closed Form: The Holy Grail of Algorithmics Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-09-25 21:35 +0100

csiph-web