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


Groups > comp.theory > #39880

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-24 20:46 -0600
Organization A noiseless patient Spider
Message-ID <sim2hr$doc$1@dont-email.me> (permalink)
References <a7c2345d-e3ab-4296-8b1b-877212aa8c7dn@googlegroups.com> <siaf08$1ft$1@dont-email.me> <e08a8e4e-5708-41c0-80b6-3def72b74fadn@googlegroups.com> <siapb5$kp9$1@dont-email.me> <3be7e146-246a-4484-bcb1-b8377d294d5dn@googlegroups.com>

Show all headers | View raw


On 9/24/2021 5:41 PM, Charlie-Boo wrote:
> On Monday, September 20, 2021 at 4:01:43 PM UTC-4, Jeff Barnett wrote:
>> On 9/20/2021 12:43 PM, Charlie-Boo wrote:
>>> On Monday, September 20, 2021 at 1:05:14 PM UTC-4, Jeff Barnett wrote:
>>>> 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
>>> Closed forms don't have a "..." operator.
>>> How is that defined, by the way?
>> It was meant to indicate "any number of", a constant. It's called an
>> ellipsis in English. In the present case you can have the exponential 1
>> deep, two deep, up to any constant number you wish deep - the depth does
>> not depend on n.
>>
>> As a side note: there is no agreed upon definition of "closed form"
>> among mathematicians, computer scientists, or philosophers. The intent
>> varies from a constant to a recursive total function definition that can
>> be evaluated in a finite number of steps with each step a finite
>> calculation. This latter requirement may be abused when dealing with
>> real numbers. For example, is PI + E a closed form? Actually is PI a
>> closed form?
>>
>> You talked about Fibonacci numbers above. You do know that that closed
>> form involves raising two irrational numbers to the nth power? It
>> happens that the sum of those powers multiplied by their coefficients
>> when added produce an integer but that is zero gain in efficiency.
>> Instead of doing about n integer additions, you must do about 2n
>> multiplies of non rationals, so what is the gain??????
>> -- 
>> Jeff Barnett
> 
>> It was meant to indicate "any number of", a constant.
> 
> There is a  much closer to formal way to define ellipsis and, if given what "conventional mathematics" means, I believe could be defined formally.
> Tell me your best way and I'll tell you mine.  It's closely related to IQ tests.

You should not be giving or taking IQ tests. Try reading more. Above you 
have many good explanations of "closed forms" and why they are not what 
you think. More study; less challenges.
-- 
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