7
$\begingroup$

Are there any interesting proofs on unconventional computing? When reading on the topic I most often see soft analysis – like following paragraph from Wikipedia (Natural computing):

Swarm intelligence,[12] sometimes referred to as collective intelligence, is defined as the problem solving behavior that emerges from the interaction of individual agents (e.g., bacteria, ants, termites, bees, spiders, fish, birds) which communicate with other agents by acting on their local environments.

Instead of soft analysis – are there any formal (and important) results in the topic?

Improve this question
$\endgroup$

4 Answers 4

Reset to default
8
$\begingroup$

A recent and interesting attempt to model flocking behavior is Bernard Chazelle's work (see the four most recent papers (as of Mar 2012). He's also running a summer school on computation and biology at the Institute for Advanced Science.

Improve this answer
$\endgroup$
5
$\begingroup$

I suggest you this survey/introduction paper (but perhaps you alredy read it):

Unconventional computing: a short introduction by M. Oltean (2009).

It is a little bit funny (see for example the "Price" column in the comparison table) ... however the references at the bottom can lead you to other relevant papers.

I'm not an expert but searching papers on other subjects I sometimes found titles about the "DNA computing" model, so - if you classify Quantum Computing conventional computing :-) - I think it is one of the most studied model, and there are many results out there (see for example "A Robust DNA Computation Model that Captures PSPACE").

I'm curious to see other answers about other weird models/results.

EDIT: I was missing a "must": Scott Aaronson's "NP-Complete Problems and Physical Reality" (2005). There is also a PowerPoint presentation ... but unfortunately no video (Scott's presentations are great, see for example a small easy introduction on (un)conventional??? quantum computing :-)

Improve this answer
$\endgroup$
1
3
$\begingroup$

There are also continuous time and analog computation models: Survey on Continuous Time Computation, Polynomial differential equation model.

Improve this answer
$\endgroup$
2
$\begingroup$

Population protocols.

The model is intuitively explained as being inspired by how a flock of birds behaves and processes information.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.