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


Groups > comp.theory > #39609 > unrolled thread

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

Started byCharlie-Boo <shymathguy@gmail.com>
First post2021-09-20 09:38 -0700
Last post2021-09-25 21:35 +0100
Articles 16 — 4 participants

Back to article view | Back to comp.theory


Contents

  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

#39609 — Converting Recursive Definition into Closed Form: The Holy Grail of Algorithmics

FromCharlie-Boo <shymathguy@gmail.com>
Date2021-09-20 09:38 -0700
SubjectConverting Recursive Definition into Closed Form: The Holy Grail of Algorithmics
Message-ID<a7c2345d-e3ab-4296-8b1b-877212aa8c7dn@googlegroups.com>
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

[toc] | [next] | [standalone]


#39613

FromJeff Barnett <jbb@notatt.com>
Date2021-09-20 11:05 -0600
Message-ID<siaf08$1ft$1@dont-email.me>
In reply to#39609
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

[toc] | [prev] | [next] | [standalone]


#39618

FromCharlie-Boo <shymathguy@gmail.com>
Date2021-09-20 11:43 -0700
Message-ID<e08a8e4e-5708-41c0-80b6-3def72b74fadn@googlegroups.com>
In reply to#39613
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?

C-B

[toc] | [prev] | [next] | [standalone]


#39621

FromJeff Barnett <jbb@notatt.com>
Date2021-09-20 14:01 -0600
Message-ID<siapb5$kp9$1@dont-email.me>
In reply to#39618
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

[toc] | [prev] | [next] | [standalone]


#39858

FromCharlie-Boo <shymathguy@gmail.com>
Date2021-09-24 16:41 -0700
Message-ID<3be7e146-246a-4484-bcb1-b8377d294d5dn@googlegroups.com>
In reply to#39621
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.

C-B

[toc] | [prev] | [next] | [standalone]


#39880

FromJeff Barnett <jbb@notatt.com>
Date2021-09-24 20:46 -0600
Message-ID<sim2hr$doc$1@dont-email.me>
In reply to#39858
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

[toc] | [prev] | [next] | [standalone]


#39622

FromBen Bacarisse <ben.usenet@bsb.me.uk>
Date2021-09-20 21:38 +0100
Message-ID<87zgs756fi.fsf@bsb.me.uk>
In reply to#39609
Charlie-Boo <shymathguy@gmail.com> writes:

> A closed form i.e. O(1) is the Holy Grail of Algorithmics.

Closed forms are rarely O(1).  First, O(1) depends on some measure.  In
comp.theory it's reasonable to expect you mean O(1) steps of a Turing
machine.  Secondly, O(1) is about an algorithm, so the "cost" of
evaluating a closed form depends on how good an algorithm you have.
I.e. I can't show you a wrong simply by showing an O(n) algorithm for
some closed form, because there might be a better one I have not thought
of.  Third, the order of an algorithm can depend on the encoding of the
"inputs" and the "outputs" so I'd have to cover every conceivable
encoding as well.

I don't have the time or the inclination to do that, so here's a
challenge...  Given the simple function f(n) = n+1, do you think there
is an encoding for n (and for the result) such that some TM M can
compute f(n) in O(1)?

The long and the short of it is that I don't think you meant to say what
you said.  That O(1) means something to you which is not the usual
technical meaning.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]


#39836

FromCharlie-Boo <shymathguy@gmail.com>
Date2021-09-24 11:10 -0700
Message-ID<34a08683-8fa6-4b71-801c-5365c7f5c5b8n@googlegroups.com>
In reply to#39622
On Monday, September 20, 2021 at 4:38:17 PM UTC-4, Ben Bacarisse wrote:
> Charlie-Boo <shyma...@gmail.com> writes: 
> 
> > A closed form i.e. O(1) is the Holy Grail of Algorithmics.
> Closed forms are rarely O(1). First, O(1) depends on some measure. In 
> comp.theory it's reasonable to expect you mean O(1) steps of a Turing 
> machine. Secondly, O(1) is about an algorithm, so the "cost" of 
> evaluating a closed form depends on how good an algorithm you have. 
> I.e. I can't show you a wrong simply by showing an O(n) algorithm for 
> some closed form, because there might be a better one I have not thought 
> of. Third, the order of an algorithm can depend on the encoding of the 
> "inputs" and the "outputs" so I'd have to cover every conceivable 
> encoding as well. 
> 
> I don't have the time or the inclination to do that, so here's a 
> challenge... Given the simple function f(n) = n+1, do you think there 
> is an encoding for n (and for the result) such that some TM M can 
> compute f(n) in O(1)? 
> 
> The long and the short of it is that I don't think you meant to say what 
> you said. That O(1) means something to you which is not the usual 
> technical meaning. 
> 
> -- 
> Ben.
Now you know that is not a formal mathematical definition.  You are really talking about allowing a recursive definition.

Yes, I mentioned that the Fibonacci function is exponentiation of real numbers - so it is way beyond what computer scientists are generally referring to.

I think of a closed form as a mathematical expression.  We just have to debate what functions are allowed.  Evaluating a mathematical function is generally considered O(1).

If everyone has gotten their fix of nitpicking, it would be nice if someone could advance to the point of addressing the question. 😊

[toc] | [prev] | [next] | [standalone]


#39837

FromCharlie-Boo <shymathguy@gmail.com>
Date2021-09-24 11:23 -0700
Message-ID<db892783-52df-4412-a28b-a26cfd9f323an@googlegroups.com>
In reply to#39622
On Monday, September 20, 2021 at 4:38:17 PM UTC-4, Ben Bacarisse wrote:
> Charlie-Boo <shyma...@gmail.com> writes: 
> 
> > A closed form i.e. O(1) is the Holy Grail of Algorithmics.
> Closed forms are rarely O(1). First, O(1) depends on some measure. In 
> comp.theory it's reasonable to expect you mean O(1) steps of a Turing 
> machine. Secondly, O(1) is about an algorithm, so the "cost" of 
> evaluating a closed form depends on how good an algorithm you have. 
> I.e. I can't show you a wrong simply by showing an O(n) algorithm for 
> some closed form, because there might be a better one I have not thought 
> of. Third, the order of an algorithm can depend on the encoding of the 
> "inputs" and the "outputs" so I'd have to cover every conceivable 
> encoding as well. 
> 
> I don't have the time or the inclination to do that, so here's a 
> challenge... Given the simple function f(n) = n+1, do you think there 
> is an encoding for n (and for the result) such that some TM M can 
> compute f(n) in O(1)? 
> 
> The long and the short of it is that I don't think you meant to say what 
> you said. That O(1) means something to you which is not the usual 
> technical meaning. 
> 
> -- 
> Ben.
O(1) means a fixed or bounded number of steps in the algorithm where each step is considered to be constant time.  So it really means constant time.

A closed form is an algorithm.  Evaluate the expression.  If you want to talk about alternate equivalent closed forms that is another question.

Encoding I/O is usually considered to be part of the program and we use standard mathematical representations for the actual I/O.

Turing Machines are at a lower level than computers in terms of how they compute and will have a hard time keeping up with them efficiency wise.

I meant that the time complexity function is a constant which is represented by 1.

[toc] | [prev] | [next] | [standalone]


#39841

FromBen Bacarisse <ben.usenet@bsb.me.uk>
Date2021-09-24 21:40 +0100
Message-ID<87r1ddyaeo.fsf@bsb.me.uk>
In reply to#39837
Charlie-Boo <shymathguy@gmail.com> writes:

> On Monday, September 20, 2021 at 4:38:17 PM UTC-4, Ben Bacarisse wrote:
>> Charlie-Boo <shyma...@gmail.com> writes: 
>> 
>> > A closed form i.e. O(1) is the Holy Grail of Algorithmics.
>> Closed forms are rarely O(1). First, O(1) depends on some measure. In 
>> comp.theory it's reasonable to expect you mean O(1) steps of a Turing 
>> machine. Secondly, O(1) is about an algorithm, so the "cost" of 
>> evaluating a closed form depends on how good an algorithm you have. 
>> I.e. I can't show you a wrong simply by showing an O(n) algorithm for 
>> some closed form, because there might be a better one I have not thought 
>> of. Third, the order of an algorithm can depend on the encoding of the 
>> "inputs" and the "outputs" so I'd have to cover every conceivable 
>> encoding as well. 
>> 
>> I don't have the time or the inclination to do that, so here's a 
>> challenge... Given the simple function f(n) = n+1, do you think there 
>> is an encoding for n (and for the result) such that some TM M can 
>> compute f(n) in O(1)?
>> 
>> The long and the short of it is that I don't think you meant to say what 
>> you said. That O(1) means something to you which is not the usual 
>> technical meaning. 
>> 
> O(1) means a fixed or bounded number of steps in the algorithm where
> each step is considered to be constant time.  So it really means
> constant time.

It has an actual meaning which is not constant time.  What you count
matters.  An algorithm that does O(1) arithmetic operations won't
necessarily be constant time (operations on large numbers might be
slower than those on small numbers).

> A closed form is an algorithm.

That's not what the phrase usually means.  If you mean an algorithm, why
not say an algorithm?  People who know what a closed form is will be
confused if you use the term to mean algorithm.

> Evaluate the expression.

There may be lots of different algorithms for evaluating the expression.

> If you want to talk about alternate
> equivalent closed forms that is another question.
>
> Encoding I/O is usually considered to be part of the program and we
> use standard mathematical representations for the actual I/O.

So pi can be represented with 100% accuracy using the standard
mathematical representation "𝞹"?  And if the "closed form" is about
square roots, the result can be "√𝞹"?

> Turing Machines are at a lower level than computers in terms of how
> they compute and will have a hard time keeping up with them efficiency
> wise.

OK.  So you are not talking about TMs.  comp.theory might be the wrong
group.  Do you have some abstract model of computation in mind?  TAOCP
using a made-up machine language to do this sort of thing.

> I meant that the time complexity function is a constant which is
> represented by 1.

You ask in the other reply if, after all this nit-picking (I would not
call it that) could people answer the question.  The question was:

  How far have people gotten in developing closed forms for recursive
  definitions starting with Fibonacci?

by which I think you mean

  How far have people gotten in developing constant time algorithms for
  recursively defined functions like Fibonacci?

Well, there are many closed form expressions for F(n) but I don't know
of any algorithms that can evaluate them in constant time.  So I think
the answer is nowhere.

If we don't allow n to be unbounded then F(n) can be evaluated in
constant time, but that's theoretically true for any function since, for
bounded inputs, we can just use a lookup table.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]


#39859

FromCharlie-Boo <shymathguy@gmail.com>
Date2021-09-24 16:45 -0700
Message-ID<db4f0bd4-b103-4c97-95ba-8ae1330c954fn@googlegroups.com>
In reply to#39622
On Monday, September 20, 2021 at 4:38:17 PM UTC-4, Ben Bacarisse wrote:
> Charlie-Boo <shyma...@gmail.com> writes: 
> 
> > A closed form i.e. O(1) is the Holy Grail of Algorithmics.
> Closed forms are rarely O(1). First, O(1) depends on some measure. In 
> comp.theory it's reasonable to expect you mean O(1) steps of a Turing 
> machine. Secondly, O(1) is about an algorithm, so the "cost" of 
> evaluating a closed form depends on how good an algorithm you have. 
> I.e. I can't show you a wrong simply by showing an O(n) algorithm for 
> some closed form, because there might be a better one I have not thought 
> of. Third, the order of an algorithm can depend on the encoding of the 
> "inputs" and the "outputs" so I'd have to cover every conceivable 
> encoding as well. 
> 
> I don't have the time or the inclination to do that, so here's a 
> challenge... Given the simple function f(n) = n+1, do you think there 
> is an encoding for n (and for the result) such that some TM M can 
> compute f(n) in O(1)? 
> 
> The long and the short of it is that I don't think you meant to say what 
> you said. That O(1) means something to you which is not the usual 
> technical meaning. 
> 
> -- 
> Ben.
> Given the simple function f(n) = n+1, do you think there
is an encoding for n (and for the result) such that some TM M can
compute f(n) in O(1)?

Certainly.  Must the relationship between the tape and the outside world be the same before and after the TM runs?
If not then it is instantaneous.

C-B

[toc] | [prev] | [next] | [standalone]


#39910

FromBen Bacarisse <ben.usenet@bsb.me.uk>
Date2021-09-25 21:31 +0100
Message-ID<875yuowg5y.fsf@bsb.me.uk>
In reply to#39859
Charlie-Boo <shymathguy@gmail.com> writes:

> On Monday, September 20, 2021 at 4:38:17 PM UTC-4, Ben Bacarisse wrote:
>> Charlie-Boo <shyma...@gmail.com> writes: 
>> 
>> > A closed form i.e. O(1) is the Holy Grail of Algorithmics.
>> Closed forms are rarely O(1). First, O(1) depends on some measure. In 
>> comp.theory it's reasonable to expect you mean O(1) steps of a Turing 
>> machine. Secondly, O(1) is about an algorithm, so the "cost" of 
>> evaluating a closed form depends on how good an algorithm you have. 
>> I.e. I can't show you a wrong simply by showing an O(n) algorithm for 
>> some closed form, because there might be a better one I have not thought 
>> of. Third, the order of an algorithm can depend on the encoding of the 
>> "inputs" and the "outputs" so I'd have to cover every conceivable 
>> encoding as well. 
>> 
>> I don't have the time or the inclination to do that, so here's a 
>> challenge... Given the simple function f(n) = n+1, do you think there 
>> is an encoding for n (and for the result) such that some TM M can 
>> compute f(n) in O(1)? 
>> 
>> The long and the short of it is that I don't think you meant to say what 
>> you said. That O(1) means something to you which is not the usual 
>> technical meaning. 
>> 
>> Given the simple function f(n) = n+1, do you think there
>
> is an encoding for n (and for the result) such that some TM M can
> compute f(n) in O(1)?
>
> Certainly.

Show it.

> Must the relationship between the tape and the outside
> world be the same before and after the TM runs?

I don't know what that means.

> If not then it is instantaneous.

Time has no bearing on any TM computations.  O(1) means that the length
of the TM configuration sequence is bounded above by a constant.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]


#39940

FromMalcolm McLean <malcolm.arthur.mclean@gmail.com>
Date2021-09-26 10:26 -0700
Message-ID<f09f3b2c-046e-4517-a036-b6248f75b7fdn@googlegroups.com>
In reply to#39910
On Saturday, 25 September 2021 at 21:31:39 UTC+1, Ben Bacarisse wrote:
> Charlie-Boo <shyma...@gmail.com> writes: 
> > Must the relationship between the tape and the outside 
> > world be the same before and after the TM runs?
> I don't know what that means.
>
If we have unary encoding, and a tape which extends in both directions,
with the number encoded left to right from the head position, there is
an easy way of calculating N +1 in a copuple of operations, as long as
the tape doesn't have a special marker on it that denotes "initial position". 

[toc] | [prev] | [next] | [standalone]


#39941

FromBen Bacarisse <ben.usenet@bsb.me.uk>
Date2021-09-26 19:02 +0100
Message-ID<87v92nrz8z.fsf@bsb.me.uk>
In reply to#39940
Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:

> On Saturday, 25 September 2021 at 21:31:39 UTC+1, Ben Bacarisse wrote:
>> Charlie-Boo <shyma...@gmail.com> writes: 
>> > Must the relationship between the tape and the outside 
>> > world be the same before and after the TM runs?
>> I don't know what that means.
>>
> If we have unary encoding, and a tape which extends in both directions,
> with the number encoded left to right from the head position, there is
> an easy way of calculating N +1 in a copuple of operations, as long as
> the tape doesn't have a special marker on it that denotes "initial
> position".

Yes.  I wonder if this is what he meant.  I left the encoding of the
output open so this is perfectly "within spec".

-- 
Ben.

[toc] | [prev] | [next] | [standalone]


#39863

FromCharlie-Boo <shymathguy@gmail.com>
Date2021-09-24 17:04 -0700
Message-ID<c509d359-07fe-4dd8-bf5a-5a82b39fd354n@googlegroups.com>
In reply to#39622
On Monday, September 20, 2021 at 4:38:17 PM UTC-4, Ben Bacarisse wrote:
> Charlie-Boo <shyma...@gmail.com> writes: 
> 
> > A closed form i.e. O(1) is the Holy Grail of Algorithmics.
> Closed forms are rarely O(1). First, O(1) depends on some measure. In 
> comp.theory it's reasonable to expect you mean O(1) steps of a Turing 
> machine. Secondly, O(1) is about an algorithm, so the "cost" of 
> evaluating a closed form depends on how good an algorithm you have. 
> I.e. I can't show you a wrong simply by showing an O(n) algorithm for 
> some closed form, because there might be a better one I have not thought 
> of. Third, the order of an algorithm can depend on the encoding of the 
> "inputs" and the "outputs" so I'd have to cover every conceivable 
> encoding as well. 
> 
> I don't have the time or the inclination to do that, so here's a 
> challenge... Given the simple function f(n) = n+1, do you think there 
> is an encoding for n (and for the result) such that some TM M can 
> compute f(n) in O(1)? 
> 
> The long and the short of it is that I don't think you meant to say what 
> you said. That O(1) means something to you which is not the usual 
> technical meaning. 
> 
> -- 
> Ben.

< Given the simple function f(n) = n+1, do you think there
is an encoding for n (and for the result) such that some TM M can
compute f(n) in O(1)?

You could compute addition in O(1).  If you are very sneaky (but not breaking any explicit rules) that could be instantaneous.

C-B

[toc] | [prev] | [next] | [standalone]


#39911

FromBen Bacarisse <ben.usenet@bsb.me.uk>
Date2021-09-25 21:35 +0100
Message-ID<87zgs0v1en.fsf@bsb.me.uk>
In reply to#39863
Charlie-Boo <shymathguy@gmail.com> writes:

> On Monday, September 20, 2021 at 4:38:17 PM UTC-4, Ben Bacarisse wrote:
>> Charlie-Boo <shyma...@gmail.com> writes: 
>> 
>> > A closed form i.e. O(1) is the Holy Grail of Algorithmics.
>> Closed forms are rarely O(1). First, O(1) depends on some measure. In 
>> comp.theory it's reasonable to expect you mean O(1) steps of a Turing 
>> machine. Secondly, O(1) is about an algorithm, so the "cost" of 
>> evaluating a closed form depends on how good an algorithm you have. 
>> I.e. I can't show you a wrong simply by showing an O(n) algorithm for 
>> some closed form, because there might be a better one I have not thought 
>> of. Third, the order of an algorithm can depend on the encoding of the 
>> "inputs" and the "outputs" so I'd have to cover every conceivable 
>> encoding as well. 
>> 
>> I don't have the time or the inclination to do that, so here's a 
>> challenge... Given the simple function f(n) = n+1, do you think there 
>> is an encoding for n (and for the result) such that some TM M can 
>> compute f(n) in O(1)? 
>> 
>> The long and the short of it is that I don't think you meant to say what 
>> you said. That O(1) means something to you which is not the usual 
>> technical meaning. 
>> 
>> -- 
>> Ben.
>
>> Given the simple function f(n) = n+1, do you think there
>> is an encoding for n (and for the result) such that some TM M can
>> compute f(n) in O(1)?
>
> You could compute addition in O(1).

O(1) what?  Using what encoding?  I think you are deliberately not
listening.

If you just want to chat, this seems like an odd way to do it.  If you
want find out how to express whatever it is you are trying to say you
will have to ask good questions and study the answers.

-- 
Ben.

[toc] | [prev] | [standalone]


Back to top | Article view | comp.theory


csiph-web