Pin Sort

Once upon a time, there were these media called punched cards. The fancy schmancy sort had a bunch of indexing holes right on the rim. If you had a particular search query, you just raised pins under the stack of cards to match your sort criteria. The cards that didn't jump up were the ones that matched.

Didn't matter how many cards you had to search - just lift the pins and you're done. A constant-time search. Try that with your new-fangled VonNeumannArchitecture and see what happens.

All the above relates to searching, not sorting, doesn't it?

All you have to do to turn this into a sort is stagger the pins by significance.

This was adapted to new-fangled VonNeumannArchitectures by Bell Labs circa 1977 and has been in use ever since for phone directory lookups...hmm, I can't at the moment find my copy of their technical report, else I'd give a more specific citation. As a result it's also in 3rd edition of Knuth, but I don't think he called it PinSort. (You may think I mean "something vaguely similar to what you're talking about", but no, I mean precisely what you're talking about.)

Cool, but I didn't think I was revealing the mysteries of the universe here. The general point is that PinSort works because of the ExFormation of the cards - not just the information encoded by 'em.

Ok, since I keep popping your bubble, here's one for you: "Kirchhoff-Lukasiewicz Logic Arrays" are, in theory, formally more powerful than TuringMachines, whereas ordinary analog computers are less powerful. (The ones that are more powerful also appear to be physically unrealizable...the original ones required physical placement of an electrode onto a surface with infinite precision and accuracy -- but there's unreleased research at http://www.cs.indiana.edu/~jwmills/ANALOG.NOTEBOOK/klm/klm.html that you could use to get your hopes up :-) -- DougMerritt

You're still not getting it. No fancy hardware is required to do Super-Turing computation. As mentioned, an interferometer does it. So does a duck. We have plentiful devices whose computations qua signal processing can't be emulated on a TM. PinSort isn't one of these - I raised it to query you about placing it into the ChomskyHierarchy.

If I don't get it, when we're talking about a mathematical field of study which you don't appear to have studied deeply as mathematics (regardless of how much you've thought about it non-mathematically), and when you're making up your own terminology with only very terse explanations of your terminology, then I think it's reasonable to conclude that anything I don't get is due to faults in your explanations (for starters, stop relying on your own private vocabulary), and further that it's much more likely that you're the one who doesn't get "it", where "it" here is the mathematics.

I've also already disputed your claim that TuringMachines can't simulate interferometers, although you probably hadn't seen that comment yet, and although I'm sure I'll need to clarify why I said so.

Searching an ordered list takes (using the binary search algorithm) O(log n) time on a sequential machine. To be more precise, it requires O(log n) comparisons.

However, on a parallel machine (with one pin, er, processing node per item to be searched), we can do that in O(1) time. Of course, it requires O(n) comparisons to pull this off--but they are all done in parallel.

Nothing remarkable about that. Nor is this observation a particularly damning indictment of Von Neumann machines; many algorithms can be made to take asymptopically less time by running them in parallel.

Your conclusion is of course accurate, but this is a particularly interesting algorithm in its own right, and is more closely related to radix sorts/searches than to compare-and-swap sorts/searches, but isn't exactly in either category. Also of interest, it happens it is one of the things that can be bitwise-parallelized -- 32 bit word used for 32 parallel searches, in a certain sense. If memory serves, AT&T did in fact build special purpose parallel hardware to speed it up further, since it was central to directory information lookups. -- Doug

Sure. If you think about it it's closely related to ordinary muxing.

As a "selection" technique this approach is still viable, it's recommended here: http://www.absolutewrite.com/novels/index_cards.htm