Most algorithms are designed for computation in a Turing machine. But Turing machines don't encompass the physics of the universe, and of course there are algorithms designed to operate with other mechanics. Let's call these other algorithms Analog Algorithms. Here's one that claims to sort a set of numbers in linear timeIf executed on a simulating Turing machine..
Algorithm Spaghetti Sort
Given an unsorted set of $n$ rational numbers $S = \{s_1, \ldots, s_n\}\quad s_i \in \mathbb{Q}$:
Obtain a set of spaghetti rods $R = \{r_1, \ldots, r_n\}\quad len(r_i) = s_i$. Form a fist around the rods.
Repeat until there are no more rods in the fist:
- Hit one end of the spaghetti rods perpendicularly against a table, such that the rods are aligned on that end.
- Lower a hand on the other side of the rods until it touches a spaghetti rod $r_i$.
- Remove the rod $r_i$ from the fist and place it at the end of the sorted output set.
Parts of this sort may seem decidedly non-linearOr at least very expensive, since we're not necessarily dealing with Turing machines.. What is the time bound for lowering a hand? How do we decide where to lower the hand from? If the hand placement is decided visually, what is the cost of synaptic transmission? And what is the cost of sensory response from the other hand touching the longest rod? How do we account for the size of a hand needed to hold a very large number of rods?
Still, the spaghetti sort seems reasonable, in at least the sense that this is how I would sort a set of spaghetti rods. And in celebration of the New Year, I propose another analog algorithm, this one solving the NP-completeProblems in the class NP are those whose solutions can be verified in polynomial time by a non-deterministic Turing machine. NP-completeness refers to the class of problems hardest in NP. Every problem in NP can be transformed to an equivalent NP-complete problem. clique problem.
Algorithm New Year's Cliquer
Given an undirected graph $G$ with vertices $V = \{v_1, \ldots, v_n\}$ and edges $E = \{v_i \leftrightarrow v_j, \ldots\}$:
Gather a group of people $P = \{p_1, \ldots, p_n\}$ and for each edge $v_i \leftrightarrow v_j = e \in E$, introduce $p_i$ and $p_j$. Ensure that each introduction results in an equivalent-strength friendship.
Institute a universal aid policy that provides each person the opportunity to visit their new friends for the New Year.
On New Year's Day, let each person $p_i$ mingle until they find a group of individuals $R_i$ where each individual in $R_i$ knows every other individual in $R_i$, and $R_i$ is the largest of all such groups. By nature of the friendships, this is guaranteed to happen.
Count the size of each group $R_j$ formed. All cliques of size $n$ in $P$ for any $n \in \mathbb{N}$ are now known. Mapping the cliques in the graph $G$ is trivial.
Have we proved $P = NP$? Definitely not. Is a New Year universal aid policy a great idea? Absolutely. Anyway, I wish you a fulfilling New Year!
