Why does sorting in computer science mean ordering rather than categorizing?
twitter.com
twitter.com
Rather, the limitation was that people didn't have the abstractions, vocabulary, and mental tools to properly conceive of general purpose computers as a concept and to understand their usefulness. They couldn't see that devices as seemingly disparate as tide prediction machines[1], census tabulation machines, and loom controllers were all instances of a single, terrifyingly general idea.
From what I can tell, Babbage mostly understood this, but it was Ada Lovelace who grasped it fully. But her writings weren't understood in her time and had to be "rediscovered" a century later. For example, she wrote [2]:
Supposing, for instance, that the fundamental relations of pitched sounds in the science of harmony and of musical composition were susceptible of such expression and adaptations, the engine might compose elaborate and scientific pieces of music of any degree of complexity or extent.
This leads me to wonder: what abstractions are we missing today that will be obvious to future generations?
BTW I have a follow-up thread on the optical telegraph, a form of networking that long predates the Internet. [3] My long-term goal is to teach a course on computing/networking/information processing before computers, with a view to extracting lessons that are still applicable today.
[1] https://en.wikipedia.org/wiki/Tide-predicting_machine
[2] https://googleblog.blogspot.com/2012/12/honouring-computings...
[3] https://twitter.com/random_walker/status/1037031465735860224
Read the history of the IBM 400 and 600 series, the business line from IBM. First machines that could add and count, then print, then multiply, then divide, and then a long struggle to get some memory. Machines had a few memory locations, then tens of memory locations, then a hundred or so. The people involved knew they could do more if they could store more info. It wasn't a conceptual problem. Finally they got to the IBM 650, with drum memory, the first business machine we'd recognize today as a computer. Knuth learned on one of those.
Read "IBM's Early Computers", von Neumann's report on the EDVAC, learn what Zuse and Atanasoff did, find an Analytical Engine simulator and learn what the machine could do, and read up on the history of punched card and tote machines.
Nevertheless, he's referring to Ada Lovelace's comments from 1843 and saying they weren't understood for ~100 years i.e. 1940s. That pre-dates most of what you're talking about.
In the twitter thread the OP clearly has read up on the history of punched cards and the history of IBM machines.
My point is that machine arithmetic preceded machine data storage. Early computing was a struggle to get something done with very, very little memory. Like 5 to 20 numbers. Babbage wanted to build something the size of a locomotive for storage - a huge drum of counter wheels, able to store 1000 numbers. Atanasoff had a rotating wheel of capacitors, refreshed on each turn, like DRAM, which was good thinking for 1939. The code-breaking machines of WWII were all very limited memory, more like a Bitcoin ASIC than a general purpose computer. IBM was plugging away with punched cards, which were their form of permanent data storage. Shannon wrote a paper on the minimum memory requirements for a telephone switch.
In the IBM punched card world, "sorting" meant ordering, and distributing into groups was "selecting". Sorting was usually required before selecting, but if you only needed two or three output groups, you could select cards using a collator, which was capable of moderately complex logic operations. You might do that for "customers who are past due", for example.
Building a stored program computer wasn't a conceptual problem. It was that, despite massive efforts, there was nothing to store the program in. The concept of algorithms dates back to at least the 9th century, and probably back to Euclid.
(Although there's a long history of programmable cam-driven machinery. I've seen the Jaquet-Droz automata. built in the 1770s, demonstrated at the museum in Neuchâtel, where they are operated once a month. That was the high point of cam driven machinery for a long time.)
> My point is that machine arithmetic preceded machine data storage.
> The concept of algorithms dates back to at least the 9th century, and probably back to Euclid.
I don't think that's the issue at hand. Special-purpose computers implement algorithms and may use arithmetic—those are not the key differentiators from general purpose computation. Perhaps they were important first steps, but clearly what e.g. Turing/Church did was something else entirely. And I'm aware Leibniz was very much concerned with the problem earlier on, but where I get a bit fuzzy is whether general purpose computers really needed the more fleshed out results of e.g. Turing (or perhaps a predecessor) in order to really build a general purpose computer—and whether that was a major limiting factor even after we had access to the necessary memory, or if we knew conceptually that what we were shooting for all along was fully general purpose computation and we were really just waiting for the hardware to be possible.
Eckert is credited with inventing delay line memory.[2] That was the first useful computer memory technology. Suddenly, everybody in number-crunching was building delay line computers - EDVAC, EDSAC, LEO, IAS, UNIVAC I... All were stored program machines. As soon as there was memory, people started putting programs in it. That's when computing took off.
[1] http://www.columbia.edu/cu/computinghistory/brennan/index.ht... [2] https://en.wikipedia.org/wiki/Delay_line_memory
Eckert it seems was inspired by Von Neumann whom he worked with on the ENIAC, and Neumann was an early appreciator of Turing's work on universal computation(from 1936)—no surprise that his eponymous architecture mirrors a universal turing machine not only in power but in form (i.e. "the concept of a computer able to store in its memory its program of activities and of modifying that program in the course of these activities"[1]).
In view of that, I'm inclined to give similar importance to Turing's theoretical work still. Maybe I'm overestimating the importance of the architectural insights it led to—but I wonder if, say, we even had the Lambda Calculus, but no Turing—would we have fully generally programmable computers as we do now (which are as general in practice as well as in theory, if that makes sense)? I'm not sure...
[1] http://www.alanturing.net/turing_archive/pages/Reference%20A...
There was a performance penalty to doing only one thing at a time, the stored program way. Stored programs have a lot of overhead - fetching instructions, decoding instructions, doing instructions that didn't directly do arithmetic - that were not present in the plugboard-wired machines. Those usually did multiple operations on each cycle. When clock rates were a few kilohertz, this mattered, a lot.
One result was a split between "scientific" and "business" computers. Scientific computers were usually binary, funded by the military, and were mostly one-off machines in the early days. Business machines were decimal, had to be cost-effective, and were mass produced. The two sides finally came together with the IBM System/360. By that point, both were stored-program.
As for an "an architecture technically capable of complete generality, but not doing it so well", that was the IBM 1401, a very successful machine with a very strange architecture. The Computer Museum in Mountain View has two of them working. It was a true stored program computer, quite different from any of the scientific computers. It had a much lower cost and parts count, and ran most of America's middle sized businesses for years.
It asserts authoritatively that is a misreading of computer science history - in history, there is rarely a single “correct reading”, but rather many interpretations that at time reinforce and at times weaken each other.
Using the imperative “read”, “learn”, etc is also heavy handed and unnecessary. It’s the kind of language bad teachers - the teachers who have to use their authority rather than mentorship skills - tend to use (“Check out those books for more” flows much better, for instance).
As a result, the comment comes a little too much across as “no, you don’t have the knowledge, I have the knowledge!” which is sadly can be a little too common in hacker circles and doesn’t really encourage open, fruitful conversations the way “You know stuff, I know other stuff, let’s put it together and see what we come up with” does.
As I was reading the GP's interpretation of these historical events, it occurred to me how difficult it really is to get at a reliable interpretation of something like this: I've already read a couple books on the subject—but I can see room the cracks so to speak, where the GP's view may be more accurate.
That said, difficulty isn't the same as impossibility—and yes, it is technically impossible (or at least meaningless) for certain definitions of 'correct' interpretation, but if you're okay with correct up to "for all intents and purposes"—then it's a non-issue. For instance, in this case there is a pretty definite question we'd like answered: which innovation was the limiting factor on our original development of general purpose computation: increased memory capacity, or theoretical knowledge of general purpose computation—or was their role more alike than different?
Depending on how things actually played out, there are definite things you can say about that. For instance, perhaps we need at least 500 bits of memory for general purpose computation—did we have access to that while no one had yet thought to build the general purpose computer because we were still waiting for Zuse, Turing/Church? If so, we answer one way; if not, we answer the other way. The only case where it gets endlessly complicated, perhaps giving apparent grounds for claiming impossibility of correct interpretation, actually fits neatly into the last option I mentioned in the original question statement: that there wasn't a significant difference in the two innovations' roles as limiting factors.
It seems valuable to understand the difficult and limits of interpretation, but I think more harm is being done than good speaking so generally of "correct readings" being impossible.
> Using the imperative “read”, “learn”, etc is also heavy handed and unnecessary. It’s the kind of language bad teachers - the teachers who have to use their authority rather than mentorship skills - tend to use (“Check out those books for more” flows much better, for instance).
I really wish this was better known. It's a pretty consistent pattern and useful to be able to recognize. My read on it is that it's typically used as a defensive strategy—a way to prevent an interlocutor from questioning the speaker any further on the subject.
Or is arguing considered rude now ?
From the guidelines:
> Be civil. Don't say things you wouldn't say face-to-face.
I don't think the comment made by Animats meets this guideline.
It is possible that OP hasn't read a sufficient amount of books, or read the wrong books, or misunderstood parts of the books he read.
The implication you are taking offense to (OP hasn't read books) does not follow from that.
> He's telling the OP to go and read up on various books with the implication that they haven't read anything on the topic.
that to me is disrespectful. But the whole tone of the comment was dismissive, so changing the first part makes it less so, but not entirely.
I wouldn't call it a politely worded comment. That's all.
This is a case of someone jumping in with both feet and not realizing they're at the wrong pool.
I think we're missing a science of meaning, and (closely related) trust.
We have a science of raw data and bits (basic thermodynamics into information theory), a science of sending streams of bits (information theory), and provide rigorous numerical bounds for e.g. if you know the medium, how quickly one can signal.
We don't have a predictive, numerical theory of meaning, which is how interpretations of data or information cohere to the real world and how those meanings can be trusted and transmitted from one another in a robust way.
We're seeing the failure of meaning all around us today as we're drowned by real data and fake data and noise, as competing voices and groups spread selfish memes and narratives that ultimately obscure truth.
We're seeing the failure of meaning as our overcompetition in academia spawns a raft of fake or non-replicable studies and p-hacking, threatening to drown the signal with noise.
Anyway, there are hints of a 'science of meaning' in different fields: Graphical statistical models hint at how causality can be inferred from downstream facts, game theory tells us some (very limited) conditions under which selfish players can learn to trust one another, evolutionary theory tells us how groups can learn to cooperate and share models of the world. But none of these provide predictive and quantitative bounds, so as of yet, meaning is an art left for cultural leaders and manipulated by advertisers and politicians, and not yet a science.
Another word for meaning could be quality. Socially and culturally, not all information is of equivalent quality and value.
In fact we use the profit motive and political power as metrics of quality, and in practice they're turning out to be a bad way to maximise long-term social value.
Maybe that was it or maybe society had not achieved a scale and a regularity where a more primitive and expension version of a programmable computer would have been useful (ie, where the cost-benefit exchange was obvious). I'd note that computers effectively came into use during WWII, where there was immense pressure to optimize the large-scale organizational activity as well as large scale industrial processes (the Manhattan Project esp).
One thing I learned in college was a means of encoding a secret: n people all learn a separate point on the curve and the degree of the polynomial for the curve, and you encode the secret as the Y-intercept. That way any k of n of those people (depending on the degree of the polynomial) can recover the secret. I thought, that’s not so hard, and I asked why this wasn’t discovered centuries ago. It’s because encoding arbitrary information as a number is an idea that never occurred to anyone before computers, aside from things like bible codes and numerology that are usually lossy anyway. But you can do this with a pad and paper if you wanted.
The one caveat is that it should be done over a finite field.
By the way, I remember you by your course on coursera, it was great. Thank you a lot for that.
The main reason I'm using Twitter for this is that it's a bit too preliminary for a blog post. I don't yet have as good an understanding of the history as I would like. This way, when I discover new stuff, I can simply add at a tweet to the thread.
But TBH I think Twitter is underrated as a publishing medium. For example, I've had probably 10x the number of responses from other people as I would have gotten in the form of blog comments.
In any case, I'm definitely planning to make this more organized once I'm happy with my level of understanding. At least a series of blog posts; probably a paper and/or online lecture.
What was your impression of the quality of those comments, compared to the ones you get on blog comments?
The first that comes to mind is rooted in the problem that our concept of "tech" is still incredibly mechanistic. Look at Foucault's "technologies of the self" and you realize that technology is not just something we create in teams at work using this or that set of tools. Rather than a "thing" outside of us, tech is very much already a part of us. We are compelled to develop it (externalize it; give it objective manifestation) simply by living.
A computer is us, but even the word computer is no longer sufficient; people needlessly mechanize humans when they think in those terms and this creates fear, fear of AI and fear of becoming mere batteries; meanwhile our fault-protection circuits have already accounted for this and we can trust them (while leaving them engaged).
We must zoom even farther out from the typical computer model in order to compute at the next level. "Tech" as an industry (in hindsight to be found a ridiculous and temporary construction) has turned too far inward. In fact there is nothing to fear outside, even in the foreign-to-tech irrational world. We can accept that world, live in it, give it the respect it seems now to unfairly demand, and learn it as a technological mode. We can bridge with it, build more technologies to abstract our relationship with it. At that point we become truly powerful, able to spin technology out of limitless resources and into limitless solutions.
> Helios: The checks and balances of democratic governments were invented because human beings themselves realized how unfit they were to govern themselves. They needed a system, yes, an industrial-age machine.
> JC Denton: Human beings may not be perfect, but a computer program with language synthesis is hardly the answer to the world's problems.
> Helios: Without computing machines, they had to arrange themselves in crude structures that formalized decision-making - a highly imperfect, unstable solution.
I really wish that the Matrix had stuck with its original concept [0] that the people were being used for their processing power, not as batteries.
[0] Or so the rumour goes.
I mean, it's such an obvious one. I must have independently thought of it a dozen times as a teenager. Hell, the movie itself sort of makes use of it - after all, AFAIR, the Matrix is simulated in peoples' heads. Why would they go with this human battery nonsense is beyond me. I guess someone with influence over the movie script must have though people are too dumb for the plot to make sense.
For example the earth was once understood to be at the center of the solar system, when telescopes could better observe planetary behavior it first lead simply to more precise epicycles.
In the book he points out that one way we tend to break through this hold on how we frame evidence, is by considering metaphors from the Arts. For example, religious writings helped inform the works of Copernicus and Newton.
So to generally answer your question, I think some insights will come to us from the Arts, like science fiction books/movies/games. For example, the show Black Mirror provides some ideas that we may at some point take for granted.
Now reading that article, one might wonder how someone could have such a solid grasp of how computing and people could work together in practice when the transistor had not yet been invented, and stored program computers were first described only a month earlier.
The reason is that Vanevar Bush had been building and working with computers for close to 20 years!
Funding ran out in large part because of cost overruns due to the fact that the technology of the time wasn’t capable of building the analytic engine design.
Wikipedia has this to say:
In 1991, the London Science Museum built a complete and working specimen of Babbage's Difference Engine No. 2, a design that incorporated refinements Babbage discovered during the development of the Analytical Engine. This machine was built using materials and engineering tolerances that would have been available to Babbage, quelling the suggestion that Babbage's designs could not have been produced using the manufacturing technology of his time.
https://www.amazon.com/Difference-Engine-Charles-Babbage-Com...
(unfortunately overshadowed in Google Search results by a William Gibson book of the same name)
It gives a lot of color on Babbage, but yes the conclusion was that Babbage design basically worked, and could have been built. There were errors in his drawings that they had to correct, but nothing fundamental.
The group at the Science Museum spent over 6 years doing this! This is the group that holds most of his papers, drafts, and unfinished machines.
Although there are a couple things I want to follow up on. They weren't that specific about what computation they did. And does it still work today? It was extraordinarily finicky. It produced a lot of bit errors, as did mechanical computing devices that came later, which sort of defeated the purpose (it was supposed to calculate tables of logarithms and such with higher accuracy than humans.)
1. The concrete computation performed was to use the Finite Difference Method (https://en.wikipedia.org/wiki/Finite_difference_method - hence the "Difference Engine" name) to calculate arbitrary polynomials of degree up to IIRC 10. By using Taylor Series, this method could be used to calculate arbitrary functions, like log and sine. This was in fact the same method used to construct logarithmic tables by hand at the time, and had similar nominal precision; the singular goal was to eliminate the bit errors rampant in the old, manual process.
2. The machine removed not just errors in calculation, but also in typesetting; about half the part-count of the original design was in its printer, which could be configured with all kinds of options for typesetting the results. It would output a "print preview" onto paper locally (this was not publicly demonstrated at the CHM because of the enormous mess of ink spills, but the machinery was run dry), and an identical wax mold ready for use in mass printing. This was because many of the bit errors in the existing log/sine/etc. tables were introduced not by the (human) computers, but by the multiple copying steps involved in transforming calculated values into printed pages.
3. Computation was quite reliable - the machine worked in base 10, and mechanisms were carefully designed to freeze up (and be easily resettable to a known-good state, as demonstrations showed) before introducing errors. As far as I know bit errors were unheard of in the demonstration runs. This reliability, like in later electronic computation, was the motivation for using digital rather than analog logic. (Finickiness was mostly limited to those halting conditions - it proved quite sensitive to clock speed (rate of crank turn), but only by the standards of the hand cranking used in demonstrations; connected up to a steam engine with 19th-century rate governors, input power could have been kept clean enough to run with long MTTF.)
I believe the better link is https://en.wikipedia.org/wiki/Divided_differences
The difference between “takes an expert engineer a month to create” and “can be CNC’d in a day” is enormous, even if the end results are the same.
Also, building something with the benefit of 150 years of technological progress gives you quite a leg up on the past even if you use techniques that would have technically been available back then.
He would still have had the problem of driving typesetting equipment, but that seems like a smaller problem. Output on punched paper tape was the solution the later generation chose, and would have worked.
Amusingly, the original telegraph inventions (plural) output dots on paper, but accidents of finance left us with the inferior audio clickery. Sort of like how we are still using x86.
The ability was potentially there, but the need perhaps was not.
It would have required a generation dedicated to that one task.
Also, although I didn't read closely enough, I think "collation" or "partitioning" is the right term for sorting things and then placing them into buckets. Sorting is just ordering, not partitioning.
Dictionaries show that "sorting" meand "ordering" in computing, but means "classifying" or "organizing" in all other contexts.
Putting documents in order is "filing", from the French word meaning "string", as in attaching things in a string to put them in order in a line.
As an example, pre-computer card catalogs are "filed", not "sorted": https://libguides.ala.org/filing-rules
Dictionaries are not authoritative sources for word definitions. Rather they are, and can only be, historical references.
Words mean what people use them to mean.
“Sort these pages” with no other instructions will almost always mean, to the average person in a general context, put the pages in ascending order using the most obvious sequence present.
“File these documents” will generally mean put these pages in their relevant folders, either in a filing cabinet or computer storage.
Well, that’s their common usage outside of computer specific applicant ions here in Australia.
YMMV
English is my second language, and to this moment, I've always believed "filing" is just "putting somewhere in the right cabinet".
For example, when a doctor files some test results, the test results aren't being put in order with other test results. Those papers are first bucketed by patient, and the buckets (files) are what's kept sorted.
https://www.asme.org/engineering-topics/articles/technology-...
Assuming that at some point we will stop writing code and machines will generate programs for us instead, then we need abstractions that make this possible: a way to describe the purpose of a program that is precise enough to generate code satisfying the purpose and that can be derived from normal human communication instead of having to be explicitly coded. In other words: a way of describing why the program exists, instead of describing what it should do.
Additionally, to avoid paperclip maximizers we would need a system of ethics and values robust enough that it becomes computable. Then it can be integrated into the code-writing code in such a way as to constrain the code it generates to only choose approaches that are in line with the value system, and to refuse to implement purposes at odds with the value system. As long as our best stab at ethics largely boils down to long lists of behavioral rules written in holy books with few underlying principles we aren't ready to build truly advanced AI.
Probably some philosopher has already figured out the right model of abstract ethics, but has gone mostly undiscovered so far.
The industry-standard term for a specification precise enough to enable building a program from it is "code"
That's a very nice question. But I tend to see it like this : if you'd know, it'd mean that somehow you predicted the future.
I'd say that abstractions are built everytime but only the good ones survive. So the only way to answer your question is to wait 50 years. Then we'll know what are those missing abstractions.
But the simple act of asking the question already opens the way to a critic of current abstractions, which will lead to new ones and maybe, one of the future :-)
Are there public places where such things are discussed ? I mean, places where you don't need to be inside a university to actually participate.
And how many people have already recognized them, only to have been ignored because they're working at too high a level for their listeners to appreciate?
I have a bit more appreciation for her insight at such an early time.
How frustrating! She could see it, but too early.
A bit like maybe Tesla, others in times just before things really opened up.
And if it hadn't, so what? The world would not have changed, we'd just have an absurdly impactical computer which no one had a use for. Had it been useful enough to keep making them and improving them, we'd have developed the abstractions.
When you have to build a device pretty much by hand, why bother building a general purpose machine?
And here we are, 181 years after Babbage first described his Analytic Engine and Aplication Specific Integrated Circuits and Graphics Processing Units are all the rage.
Because you'd conquer many industries with it simultaneously. Instant path to richness.
> And here we are, 181 years after Babbage first described his Analytic Engine and Aplication Specific Integrated Circuits and Graphics Processing Units are all the rage.
It's a different thing. We usually first figure a description of a computation - one that could be run on a general-purpose machine - and then turn it into ASIC to make it more efficient, by performing only the work necessary for that one particular calculation. Back in Babbage's times, they didn't have a coherent notion of computation yet.
I just mean to say, from my limited knowledge, the available applications were all (mostly?) bespoke anyways, so the inputs and outputs probably needed to be also. So perhaps a modular mechanical general purpose computer may have helped.
> It's a different thing.
Yes, you've made a good point, I agree. Perhaps, then, if you were to build a general purpose mechanical computer ~180 years ago you might use it for whatever application is required, observe it's most commonly used computational paths, then swap it out for an application specific computer. of (possibly?) reduced complexity. You can then take your whizz-bang-high-tech-expensive computer to the next client, rinse and repeat. Maybe.
That's what I was imagining when writing that comment. And I suppose experience turning computation into work in one industry would let you design bespoke endpoints for another faster.
For one, both quantum computing and general relativity have some concepts that are extremely hard to grasp by the mind imho
(Though now that I think about it, it's both: if I handed a random non-coder a deck of cards and asked them to sort them, I'd expect them to group by suit and then order by value. I wouldn't expect four stacks by suit in random order, or a deck of all the cards in numerical order regardless of suit...)
That nitpick aside, it was a good excuse to get into the interesting pre-digital computing history stuff.
Dictionary.com has it as "to arrange according to sort, kind, or class; separate into sorts; classify". I looked it up in the OED too -- mostly because we have one and I don't get enough excuses to use its nifty little magnifying glass -- and it also supports the notion that it means by category, not by order. The general verb definition is "to arrange things according to kind or quality", and there's a separate definition for software: "sort: Computers: the action of arranging items of data in a prescribed sequence".
I think I've always thought of ordering as a subset of sorting, not something different, both in computing and in "real life" language use.
When sorting washed laundry I categorise by type and order by a fairly arbitrary mix of target position (undies in the top left draw, socks top right, daily t-shirts the draw below, "better" t-shirts the draw below that, then trousers, ...), hue/pattern/subject, and a few other properties. As with your cards example there are both grouping and ordering operations present in the sorting operation (in the cards example there might be two orderings: one for the suits if you want them to be in a specific order and one by the value of the cards within the suit).
Sorting numbers in a computer seem quite different: each category has at most one item and the are ordered by the same property they are categorised by, but the process is similar enough.
And sorting in computing is not always simply ordering. There are many examples where it is categorising (just by some variety of ordinal value). Some sorting algorithms explicitly categorise the input data as a divide-and-conquer process. Sometimes you don't care about the precise ordering (but it is done precisely anyway because a fuzzy sort would be no more performant).
The only examples that immediately jumps to mind where there is a definite distinction made are data management languages where there is a distinction between ordering and grouping (quite explicitly seen in SQL's "order by" and "group by" clauses), and even there I know that internally ordering/grouping/both are performed by what I would identify as a sort operation.
Sorting doesn't mean something different in computing really, people just tend to pick out a more specific definition in that context.
If I was sorting lego blocks I don't know if I would do it first by color and then by size/shape (here are all the 2x8s, here are all the 1x4s, etc.), but it would definitely be by category.
size/shape is far more useful.
Go ask your wife how she sorts the laundry.
Most languages are context sensitives, but generalized computing is fundamentally defined by a context free language in which a processing transition can execute and not care was previous states were. This gets blurry with recursion and generics and other syntactic sugar, but fundamentally state changes are still defined by the operation and instantaneous state and not the language itself.
So in our context-free language of generalized computers, sorting and ordering are the same.
What on Earth do you mean when you say “generalized computing is fundamentally defined by a context free language in which a processing transition can execute and not care was previous states were”?
Perhaps you are just writing context free/sensitive when you mean something different from “the set of words that may be formed by starting with some nonterminal symbol S, following rules of the form A -> xy where A is any nonterminal and x and y are either terminal or nonterminal symbols, repeating until there are no nonterminals left.”
If you really mean something about all computations being expressible in a context free language then I suppose I would have to agree but I put it to you that a regular language would be sufficient.
The other thing I can’t understand is what this has to do with either the parent or the article?
Someone else posted a much more readable version, but it is buried under a downvoted post:
Except that it is Romance or Romanic languages, not Romantic languages.
There does seem to be widely-attested noun forms like French sorte, Italian sorta with a meaning along the lines of "type" or "kind".
[0] http://www.anglo-norman.net/gate/
greetings, eMBee
If the categories have a natural order, then people will exploit that when they sort.
Suppose you had to put some cards with names on them into bins labeled by first letter. You might go through the cards one by one and stick each in the appropriate bin. It would help you if the bins are in alphabetic order, rather than scrambled.
Sorting into categories involves a search to find the category for an item; the search benefits from order.
…and infinite categories.
Which was what I expected. The twitter post seems to suggest that his expectation for the given question would be four decks, one for each suit (i.e., categorized).
> Merging (or collating) means the combination of two or more ordered files into a single ordered file.
So it's not quite the same idea.
I hate to post anything longer than random thoughts on Twitter, but this is an unfortunate consequence of the culture shift in past 10 years driven by the social media giants. Like it or not, Twitter is now the center of gravity of the entire Internet, and currently the most effective online platform to make posts with high visibility is Twitter...
Other platforms like forums declined, even forums did nothing wrong by themselves, and they are in fact much more suitable for real discussion. But the culture is already changed, people got used to make random 20 words posts on their mobile phones instead of reading a long threads of discussion, microblog-like, social-media-like platforms would prevail in the shortterm future. The only thing we can do is to promote a OStatus-based, open, alternative social media implemented by GNU/Social, Mastodon, etc, to make the situation less harmful.
I'm happy that we can still have real discussion on Hacker News.
Ultimately, if Twitter is the center of gravity of the internet, then Pluto must be the center of gravity of our solar system. The only reason I mention this is because I find people make the sort of arguments like you're making to convince themselves that they're not just wasting time on these platforms. I don't think there's been any shift in culture. There probably has been a shift in demographics as the internet has become much more common among less technically oriented individuals, but I think the real player is simply that these platforms are designed to be addictive, and they are. People keep using them even when they want to quit or do not find the time spent on them beneficial. Dopamine's a hell of a drug.
[1] - http://www.pewinternet.org/2016/11/11/social-media-update-20...
[2] - https://venturebeat.com/2018/07/27/twitter-loses-1-million-m...
Journalists and celebrities certainly seem to think so, and I'm glad they do, because I can easily avoid them by simply ignoring Twitter.
I had a strange professional experience encountering media school academics about 5-7 years ago who were all so gung-ho about it. This was when the "firehose" could be acquired with a budget plausible within a grant-funded research group, and they seemed to imagine themselves having total information awareness like they had joined the five eyes. They spoke as if they were on the cusp of a future where this tool replaced all other forms of polling and data-gathering for social science, with no apparent concern for the incompleteness of this perspective nor of the ethical quandaries if it really were that powerful.
> This is great stuff, too bad it's on Twitter instead of a real website or platform.
https://www.merriam-webster.com/words-at-play/tweeting-up-a-...
Perhaps a more illustrative example is the word "or", in plain english it normally means an "exclusive or", but in CS it means an "inclusive or".
- stable sort of unique values is ordering
- stable sort of non-unique values is categorization + ordering; this is a most general algorithm which could reasonably be used for either operation
- non-stable sort of non-unique values is categorization without ordering
- non-stable sort of unique values technically could be implemented as a NOP.
Given that various strategies of ordering and categorizing have different trade-offs between {memory,computational} complexity, and linear vs random access patterns, it makes sense to consider them pluggable algorithms that can be swapped depending on requirements.
"The blocks were sorted by size" implies that there is some metric, and again, it's pretty clear in context.
Isn't that today's Free Space Optical Communications? Bandwidth is measured in Gigabits per second.
https://en.wikipedia.org/wiki/Free-space_optical_communicati...
For example, consider an array of one million arbitrary alpha-numeric strings. If you were to sort them by category, would that mean simply making contiguous regions of the array where each string begins with the same character?
Few people would claim that each position in an order is a different category. And if I asked someone to categorise a pile of papers and they handed me back a single stack, I'd be unimpressed.
That said, the details about old school punch card sorting is pretty neat.