Friam

Analog Computing Theory

Classic

List

Threaded

7 messages Options

Owen Densmore

Analog Computing Theory

Administrator

In our Mathematical Thinking seminar (on computer science) today, the
topic of Analog computing came up.

Do we have a good foundational approach to analog computing? For
example, analog automata, computational theory on decidability for
analog computers, a notion of analog computational complexity?

-- Owen

============================================================
FRIAM Applied Complexity Group listserv
Meets Fridays 9a-11:30 at cafe at St. John's College
lectures, archives, unsubscribe, maps at http://www.friam.org

Tom Carter

Re: Analog Computing Theory

Owen -

An interesting paper on some of these issues (you may recognize the author :-) :

http://eprints.kfupm.edu.sa/36302/1/36302.pdf

But, possibly more fun:

http://books.google.com/books?id=XW7fICYtkg8C&pg=PA223&lpg=PA223&dq=spaghetti+dewdney&source=bl&ots=fXNU7klBKJ&sig=z3hibL7KkO-WG1ewPLzfNn9HmxU&hl=en&ei=7wqrS9-oNIT6sgPsj_TPDQ&sa=X&oi=book_result&ct=result&resnum=2&ved=0CAkQ6AEwAQ#v=onepage&q=&f=false

(if that link is too messy, google spaghetti dewdney , and click the google books link for The (new) Turing omnibus)

Some exercises:

1.) Design a device to find the maximum of a set of real numbers in 1 step. (hint: spaghetti)

2.) Find the maximum length path in a tree in 2 steps.

3.) Evaluate the validity of this algorithm for finding the maximum (no loops) path between two given vertices in a connected graph:

a. Make the graph out of string/wire (see Dewdney . . .)

b. Hold the two vertices, one in each hand, and pull taut. Cut one (taut) link that doesn't separate the graph.

c. Repeat step b. until there are no more links that can be cut without separating the graph.

d. The remaining taut line between the two vertices is the desired path. (or is it???)

Note: How can you make sure that cutting a particular link doesn't separate the graph? (hint: wire . . . :-)

For the more philosophically inclined:

http://homepages.ipact.nl/~lokhorst/hypercomputationUCL.pdf

And, a reference link for the future:

http://www.mdpi.com/journal/computers/special_issues/analogcomp

tom

On Mar 24, 2010, at 9:25 PM, Owen Densmore wrote:

> In our Mathematical Thinking seminar (on computer science) today, the topic of Analog computing came up.
>
> Do we have a good foundational approach to analog computing? For example, analog automata, computational theory on decidability for analog computers, a notion of analog computational complexity?
>
> -- Owen
>
>
>
> ============================================================
> FRIAM Applied Complexity Group listserv
> Meets Fridays 9a-11:30 at cafe at St. John's College
> lectures, archives, unsubscribe, maps at http://www.friam.org
>

============================================================
FRIAM Applied Complexity Group listserv
Meets Fridays 9a-11:30 at cafe at St. John's College
lectures, archives, unsubscribe, maps at http://www.friam.org

Tom Carter

Re: Analog Computing Theory

p.s. -

A couple more interesting links:

http://www.scottaaronson.com/papers/npcomplete.pdf

(question: anybody out there tried "anthropic computing"? :-)

and (some of what prompted the above):

http://kryten.mm.rpi.edu/scb_pnp_solved22.pdf

(consider the risks of careless reading . . . could this be a new entry in the "next Sokal" sweepstakes?)

tom

On Mar 25, 2010, at 12:49 AM, Tom Carter wrote:

> Owen -
>
> An interesting paper on some of these issues (you may recognize the author :-) :
>
> http://eprints.kfupm.edu.sa/36302/1/36302.pdf
>
> But, possibly more fun:
>
> http://books.google.com/books?id=XW7fICYtkg8C&pg=PA223&lpg=PA223&dq=spaghetti+dewdney&source=bl&ots=fXNU7klBKJ&sig=z3hibL7KkO-WG1ewPLzfNn9HmxU&hl=en&ei=7wqrS9-oNIT6sgPsj_TPDQ&sa=X&oi=book_result&ct=result&resnum=2&ved=0CAkQ6AEwAQ#v=onepage&q=&f=false
>
> (if that link is too messy, google spaghetti dewdney , and click the google books link for The (new) Turing omnibus)
>
> Some exercises:
>
> 1.) Design a device to find the maximum of a set of real numbers in 1 step. (hint: spaghetti)
>
> 2.) Find the maximum length path in a tree in 2 steps.
>
> 3.) Evaluate the validity of this algorithm for finding the maximum (no loops) path between two given vertices in a connected graph:
>
> a. Make the graph out of string/wire (see Dewdney . . .)
>
> b. Hold the two vertices, one in each hand, and pull taut. Cut one (taut) link that doesn't separate the graph.
>
> c. Repeat step b. until there are no more links that can be cut without separating the graph.
>
> d. The remaining taut line between the two vertices is the desired path. (or is it???)
>
> Note: How can you make sure that cutting a particular link doesn't separate the graph? (hint: wire . . . :-)
>
>
>
> For the more philosophically inclined:
>
> http://homepages.ipact.nl/~lokhorst/hypercomputationUCL.pdf
>
> And, a reference link for the future:
>
> http://www.mdpi.com/journal/computers/special_issues/analogcomp
>
> tom
>
> On Mar 24, 2010, at 9:25 PM, Owen Densmore wrote:
>
>> In our Mathematical Thinking seminar (on computer science) today, the topic of Analog computing came up.
>>
>> Do we have a good foundational approach to analog computing? For example, analog automata, computational theory on decidability for analog computers, a notion of analog computational complexity?
>>
>> -- Owen
>>
>>
>>
>> ============================================================
>> FRIAM Applied Complexity Group listserv
>> Meets Fridays 9a-11:30 at cafe at St. John's College
>> lectures, archives, unsubscribe, maps at http://www.friam.org
>>
>
>
> ============================================================
> FRIAM Applied Complexity Group listserv
> Meets Fridays 9a-11:30 at cafe at St. John's College
> lectures, archives, unsubscribe, maps at http://www.friam.org
>

lrudolph

Re: Analog Computing Theory

In reply to this post by Owen Densmore

Owen asks:

> Do we have a good foundational approach to analog computing? For
> example, analog automata, computational theory on decidability for
> analog computers, a notion of analog computational complexity?

I don't know what values to assign to "we" and "good" to
make the answer "yes"; but there is, for instance, a
somewhat lively continuing effort by Smale, Shub, and Blum
(in various combinations and with other collaborators)
on foundational (and implementation) issues related to
computation with real numbers (that's *real* real numbers,
not floating point or the like), and there's also been
an effort (which I think is now less lively, but I may
just be out of touch) somehow mixing differential equations
with (non-)recursive function theory...if I can track down
anything more about the latter, before someone else does,
I'll update all y'all. (Meanwhile you can look up
"Blum-Shub-Smale machines" and see if they are relevant
to your intentions.)

============================================================
FRIAM Applied Complexity Group listserv
Meets Fridays 9a-11:30 at cafe at St. John's College
lectures, archives, unsubscribe, maps at http://www.friam.org

glen e. p. ropella-2

Re: Analog Computing Theory

In reply to this post by Tom Carter

Thanks for all these links!

Tom Carter wrote circa 10-03-25 12:49 AM:
> For the more philosophically inclined:
>
> http://homepages.ipact.nl/~lokhorst/hypercomputationUCL.pdf
>
> And, a reference link for the future:
>
> http://www.mdpi.com/journal/computers/special_issues/analogcomp

Tom Carter wrote circa 10-03-25 01:54 AM:

> p.s. -
>
> A couple more interesting links:
>
> http://www.scottaaronson.com/papers/npcomplete.pdf
>
> (question: anybody out there tried "anthropic computing"? :-)
>
> and (some of what prompted the above):
>
> http://kryten.mm.rpi.edu/scb_pnp_solved22.pdf

--
glen e. p. ropella, 971-222-9095, http://agent-based-modeling.com

============================================================
FRIAM Applied Complexity Group listserv
Meets Fridays 9a-11:30 at cafe at St. John's College
lectures, archives, unsubscribe, maps at http://www.friam.org

Sarbajit Roy (testing)

Re: Analog Computing Theory

In reply to this post by Tom Carter

Hi

I'm an engineer (so not really a scientist). Was just mulling if
everything on this list has to be "complex" (ie. made complicated) by
converting / reducing to simple mathematical "models" (with loads of
assumptions) to solve problems, which nobody (or hardly anyone) faces
in the real world, on inappropriate machines.

Analog computers IMO could include many practical (but now obsolete)
devices like a) analog PID controllers b) firing trajectory
controllers c) range finders etc.

Sarbajit Roy

On 3/25/10, Tom Carter <[hidden email]> wrote:

> Owen -
>
> An interesting paper on some of these issues (you may recognize the author
> :-) :
>
> http://eprints.kfupm.edu.sa/36302/1/36302.pdf
>
> But, possibly more fun:
>
>
> http://books.google.com/books?id=XW7fICYtkg8C&pg=PA223&lpg=PA223&dq=spaghetti+dewdney&source=bl&ots=fXNU7klBKJ&sig=z3hibL7KkO-WG1ewPLzfNn9HmxU&hl=en&ei=7wqrS9-oNIT6sgPsj_TPDQ&sa=X&oi=book_result&ct=result&resnum=2&ved=0CAkQ6AEwAQ#v=onepage&q=&f=false
>
> (if that link is too messy, google spaghetti dewdney , and click the
> google books link for The (new) Turing omnibus)
>
> Some exercises:
>
> 1.) Design a device to find the maximum of a set of real numbers in 1
> step. (hint: spaghetti)
>
> 2.) Find the maximum length path in a tree in 2 steps.
>
> 3.) Evaluate the validity of this algorithm for finding the maximum (no
> loops) path between two given vertices in a connected graph:
>
> a. Make the graph out of string/wire (see Dewdney . . .)
>
> b. Hold the two vertices, one in each hand, and pull taut. Cut one
> (taut) link that doesn't separate the graph.
>
> c. Repeat step b. until there are no more links that can be cut
> without separating the graph.
>
> d. The remaining taut line between the two vertices is the desired
> path. (or is it???)
>
> Note: How can you make sure that cutting a particular link doesn't
> separate the graph? (hint: wire . . . :-)
>
>
>
> For the more philosophically inclined:
>
> http://homepages.ipact.nl/~lokhorst/hypercomputationUCL.pdf
>
> And, a reference link for the future:
>
> http://www.mdpi.com/journal/computers/special_issues/analogcomp
>
> tom
>
> On Mar 24, 2010, at 9:25 PM, Owen Densmore wrote:
>
>> In our Mathematical Thinking seminar (on computer science) today, the
>> topic of Analog computing came up.
>>
>> Do we have a good foundational approach to analog computing? For example,
>> analog automata, computational theory on decidability for analog
>> computers, a notion of analog computational complexity?
>>
>> -- Owen
>>
>>
>>
>> ============================================================
>> FRIAM Applied Complexity Group listserv
>> Meets Fridays 9a-11:30 at cafe at St. John's College
>> lectures, archives, unsubscribe, maps at http://www.friam.org
>>
>
>
> ============================================================
> FRIAM Applied Complexity Group listserv
> Meets Fridays 9a-11:30 at cafe at St. John's College
> lectures, archives, unsubscribe, maps at http://www.friam.org
>

Owen Densmore

Re: Analog Computing Theory

Administrator

On Mar 26, 2010, at 11:59 PM, sarbajit roy wrote:
> Hi

Welcome!

> I'm an engineer (so not really a scientist). Was just mulling if
> everything on this list has to be "complex" (ie. made complicated) by
> converting / reducing to simple mathematical "models" (with loads of
> assumptions) to solve problems, which nobody (or hardly anyone) faces
> in the real world, on inappropriate machines.

We started late 2002, meeting here in Santa Fe for coffee Friday
mornings to chat about complexity science .. things related to the
Santa Fe Institute's work.

The list started as a way to continue the chat on-line, and to
announce things like changes in venue etc.

It grew over time to be very wide spread, I think we're well over 400
now.

Our conversations are all over the map, as you are discovering! :)

The Analog question came about because a few of us are interested in
theoretical computer science, and during one of Nick Thompson's
seminar series, a question was asked about the state of analog
computer science. For example is there a computational complexity
hierarchy for analog computing? Are there decidability issues? Is
there a suite of automata under study?

One example question could be: Is there the equivalent problem to the
Halting Problem in the analog domain? In digital computers, we can
prove the number of programs is in the countably infinite domain,
while the "languages" that can be recognized by digital computers is
in the continuum. Thus the gap would suggest unsolvable problems for
digital computers.

Is the same true for analog?

> Analog computers IMO could include many practical (but now obsolete)
> devices like a) analog PID controllers b) firing trajectory
> controllers c) range finders etc.

It is interesting that they fell out of style, given their possible
strengths.

> Sarbajit Roy

-- Owen

============================================================
FRIAM Applied Complexity Group listserv
Meets Fridays 9a-11:30 at cafe at St. John's College
lectures, archives, unsubscribe, maps at http://www.friam.org