Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.theory > #39609 > unrolled thread
| Started by | Charlie-Boo <shymathguy@gmail.com> |
|---|---|
| First post | 2021-09-20 09:38 -0700 |
| Last post | 2021-09-25 21:35 +0100 |
| Articles | 16 — 4 participants |
Back to article view | Back to comp.theory
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
| From | Charlie-Boo <shymathguy@gmail.com> |
|---|---|
| Date | 2021-09-20 09:38 -0700 |
| Subject | Converting 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]
| From | Jeff Barnett <jbb@notatt.com> |
|---|---|
| Date | 2021-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]
| From | Charlie-Boo <shymathguy@gmail.com> |
|---|---|
| Date | 2021-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]
| From | Jeff Barnett <jbb@notatt.com> |
|---|---|
| Date | 2021-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]
| From | Charlie-Boo <shymathguy@gmail.com> |
|---|---|
| Date | 2021-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]
| From | Jeff Barnett <jbb@notatt.com> |
|---|---|
| Date | 2021-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]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2021-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]
| From | Charlie-Boo <shymathguy@gmail.com> |
|---|---|
| Date | 2021-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]
| From | Charlie-Boo <shymathguy@gmail.com> |
|---|---|
| Date | 2021-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]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2021-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]
| From | Charlie-Boo <shymathguy@gmail.com> |
|---|---|
| Date | 2021-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]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2021-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]
| From | Malcolm McLean <malcolm.arthur.mclean@gmail.com> |
|---|---|
| Date | 2021-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]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2021-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]
| From | Charlie-Boo <shymathguy@gmail.com> |
|---|---|
| Date | 2021-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]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2021-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