(Guest post by By Jeffery D. Stein, Chairman, IT History Society (info@ithistory.org), but first a related post by me.)
POST BY ME:
- Often you find that the origin of your field is from a different field. Ramsey's paper where he proved (what is now called) Ramsey's theorem was actually a paper in logic, though he did say that his combinatorial lemma may be of independent interest. Knowing what he was working on expands your horizons.
- If you study some history and then look around at the present world you will see some things in a different light. For example, if you study the history of Group Theory you realize that they didn't just write down some axioms and see where they led- they had actual applications in mind (e.g., showing the quintic had no solution in radicals). The axiomatic approach is fairly recent.
- When teaching (say) cardinality it is good to know that this concept was once controversial and some mathematicians disagreed with it. Hence be patient with your students. I tell them that this concept was troubling and some of the controversy around it.
- You can pick up some factoids of interest (and if you learn more about them they can become facts). I read an interview with Sheila Greibach (early Formal Lang Theorist) and, in passing, she mentions that any r.e. set can be written as the intersection of two context free languages. I never knew that! The other direction- the intersection of two context free Languages is an r.e. set is easy, but good to know for a HW or Exam question. (NOTE ADDED LATER- a commenter pointed out, correctly, that this cannot be correct. I will check what she actually wrote later.)
- The items above are actually about the history of the IDEAS and not the people. Knowing something about the people can be interesting, but is likely less useful for research and teaching. If you disagree I would love to hear a respectful counterargument.
GUEST POST: Introducing an IT Teaching and Research Resource
Guest Post by Jeffery D. Stein, Chairman, IT History Society (info@ithistory.org)
In 2007, the IT History Society was formed. The Society is dedicated to informing IT companies about the value in preserving their history, helping archivists to be more effective in their work in preserving IT history, and most importantly being a reference point for the many international places of computing history information.
The Society wants to assist educators, students of information technology, and researchers in learning more about the history and background of the information technology industry, an industry that has had a significant effect on mankind in the past seven decades. It has nearly 700 international institutional and individual members (no charge to be a member). Institutional members include IBM, HP, Intel, the Smithsonian Institution, Computer History Museum, Charles Babbage Institute, MIT, Caltech, Hans Nixdorf Museum, British Library, Stanford Silicon Valley Museum, Deutsches Museum, IEEE History Center, UK National Archive, Hagley Museum, and more. Individual members include historians, computer scientists, and people who have worked in the industry from various countries. Currently the Society has many online databases; but, two in particular may be of great value for teaching information technology and research:
- IT Historical Resource Sites Database. over 400 and growing every day, sites that have historical information about the information industry. This entire database is completely indexed and searchable, which can be a beneficial aid in targeted search and research.
- IT Honor Roll is database of over 800 names and growing, discussing individuals who have made a noteworthy contribution to the information technology industry.
- Calender of upcoming IT Historical and Archival events
- Research links and tools to aid in the preservation of IT history
- Over 1,000 Technology Quotes
- An active Blog with discussions about historical IT events and the people behind them
- A Social Network of IT history professionals, archivists, and hobbyists.
The Society feels that these valuable resources can be of great benefit to information technology professors, teachers, assistants, researchers, and students. All databases are works in progress and each database has links for the IT community to add and grow the entries of each database. The Society is a non-profit educational and research organization. It does not charge for membership or the use of its information. The IT community supports our operations through donations to our 501 (c) (3) non-profit foundation. Please visit this link for further information.
"any r.e. set can be written as the intersection of two context free languages"
ReplyDeleteWhat am I missing here? Every context-free language is decidable. The decidable languages are closed under intersection. So the intersection of any two context-free languages is decidable. Therefore any undecidable r.e. language is not the intersection of two context-free languages.
Context free languages are not closed under intersection (the wikipedia proof suffices ... consider A={a^n b^n c^m| n,m>=0} and B={a^m b^n c^n| n,m>=0} ... A intersect B = { a^n b^n c^n, n>=0 } which is not c.f. by the pumping lemma.
DeleteI'm not sure where you got the decidable languages are closed under intersection ... I'm aware of it holding for regular languages ...
The citation for the theory in the quotation is (Ginsburg et al., 1967)
AH- you are correct. I will double check what is says;
ReplyDeletehowever, my issue is at home.
IEEE Annals of the History of Computer Science, 1981,
Volume 3 has an issue devoted to theory.
I could not find it on line but if someone else does please check what she wrote.
It is well-established that the serious study of history and mathematics both are historically associated to the advancement of radical agendas.
ReplyDeleteFor example, IAS historian Jonathan Israel concludes the Introduction to his just-published Democratic Enlightenment: Philosophy, Revolution, and Human Rights, 1750-1790 (Oxford University Press, 2011) with the following quotation from the 18th century polymath Paul-Henri Thiry, Baron d'Holbach:
------------
“If error and ignorance have forged the chains of peoples, if prejudice perpetuates them, science, reason and truth will one day be able to break them.”
[Israel concludes …] A noble and beautiful thought, no doubt, but was he [d'Holbach] right? That was and remains today the unresolved challenge of the Radical Enlightenment.
------------
Following-up Prof. Israel's question, we are led naturally to ask, to what extent do modern-day weblogs like Computational Complexity, Gödel's Lost Letter, Shtetl Optimized, Combinatorics and More, and The Opinions of Doron Zeilberger (plus the newly reborn Quantum Pontiff and many more) all serve to advance — whether deliberately or unwittingly — the various technologically and socially radical objectives of humanity's ongoing Enlightenment?
The answer varies obviously with the individual readers of these weblogs, and (to express my own opinion) when read with an eye to systems engineering objectives and enterprises … well … modern computational complexity theory is a white-hot nexus of transformational ideas and tools that already are greatly accelerating the 21st century's d'Holbach-style enterprises … and promise further, still greater accelerations in decades to come.
For which, appreciation and thanks are extended to Lance and GASARCH … and to Jeffrey Stein for encouraging us all to appreciate the radical historical context that is ancestral to all of today's radical mathematical advances. :)
About the r.e. representation bit, I don't have the issue at hand either, but I'm pretty sure the actual formulation was more like "Any r.e. set can be written as the homomorphic image of the intersection of two deterministic context-free languages."
ReplyDelete@anon: Wouldn't it be true that ""Any r.e. set can be written as the homomorphic image of one deterministic context-free language"?
ReplyDeleteI guess this is the usual exercise that checking emptiness of intersection of two CFLs is undecidable.
ReplyDelete@sidle , u keep on making the same mistakes ... keep ur posts short . oh dear, if I had a wife, and that wife would post on bloggers, then I presume her volume would equate half as much as urs. sigh.
ReplyDelete@Anonymous@1:11PM: No it wouldn't: context-free languages are closed under homomorphisms.
ReplyDeleteAnonymous, perhaps systems engineers are prolix by nature. After all, we idealize dynamical processes as being microscopically reversible yet macroscopically irreversible (this includes computation processes) … we view macroscopic processes generically as separations … and about separations there is much to be said … as every complexity theorist knows. :)
ReplyDeleteThe IEEE Annals of the History of Computer Science,
ReplyDeleteVolume 3, No 1, Jan 1981
has an article by Sheila Greibach entitled
Formal Languages: Origins and Directions.
Page 32 has the following:
What happens if the acceptor is allowed to have multiple storage tapes?
One-way nondeterministic acceptors with n tapes, tape i of Scheme i, define
precisely the class of homomorphic images of the
intersection of n languages. The ith language definable by a realtime
acceptor of Scheme i; limitations on the computation time of the acceptor
correspond to limitations on the erasing done by the homomorphism
(Greibach and Ginsburg 1972; work done in 1968)
This generalizes the observation that every recursively enumerable set
can be obtained as the intersection of two deterministic CF languages
(Ginsberg, Greibach, and Harrison 1966); a corresponding result just
for quasi-realtime multipushdown store automata was used to show that
NTIME(n) is contained in the family of scattered context languages
(Greibach and Hopcroft 1969).
Ginsberg, Greibach, Harrison 1966 was a conference paper whose
journal version is titled One Way Stack Automata and is in
JACM Volume 14, 1967,
SO, what to make of all of this?
Greibach is incorrect (the intersection of any two CFL's is decidable);
however, I think she meant homomorphisms
of the intersection of CFL's. The homorphisms can erase,
so the image need not be decidable.
GASARCH asks "What of make of all this?"
ReplyDeleteWe can IT history narrowly as the history of ideas that lead to good theorems, or we can read it broadly as the history of ideas that lead to good enterprises (including theorem-proving). And needless to say, it's neither feasible nor desirable that everyone read IT history the same way.
For example, even the most scrupulously pure-minded complexity theorists are sobered by today's global economic climate. As the ardently pro-capitalist economist Umair Haque (who is the Scott Aaronson of 21st century economic theory) writes in this week's HBR blog:
----------------------
Was Marx Right?
“Prosperity as we know is lazily circling the glowing inner rim of the burbling event horizon of a massive supergalactic black hole. And when it comes to doing much about it (wave hello to your new friend, ‘double-dip’), well, the status quo’s pretty much out of options, out of ideas, and running out of time (hey, is that a Congressional “super-committee” being stalked by lobbyists I see? Who came up with this brain-melter of an idea?).”
“Wages in many advanced economies — notably, the most purely capitalist in a financialized sense — have failed to keep pace with productivity; not for years, but for decades (America’s median wage has been stagnant for roughly 40 years).”
----------------------
In the light of IT history, it is natural to ask: Do the theorems of modern complexity theory have any concrete relevance to addressing the problems that Umair's essay identifies?
Perhaps one pretty good answer is that some people think so and everyone hopes so. :)
@gasarch: The JACM paper also says "homomorphic image" (Theorem 3.1). Let's say the extract you give from IEEE Annals might also be understood as to imply "homomorphic image".
ReplyDeleteThis post is in response to John Sidles’ last post regarding Umair's economic black holes.
ReplyDeleteIf I were an economist, I would take a closer look at the black hole effect of hedge funds.
A superficial analysis goes something like this:
1. One of the top dogs in the hedge fund world made $5 Billion in 2010. He was also one of the top earners in 2007 at +$3 Billion.(He keeps most of it because he is taxed at 15% rate for capital gains.)
2. In 2007 he seems to have made a fortune helping to package and sell junky mortgages and other stuff backed by credit default swaps.
3. In 2010, he made a bigger fortune betting against credit default swaps and guessing (with a little help from his friends) that the Federal Government would be forced to acknowledge that AIG was “too big to fail” and then have to pay out on the credit default swaps.
4. It doesn’t take a computer scientist (Lance’s tweet 5 days ago) to figure out that the Feds and the taxpayers may have been out gamed by a relatively small cast of “greed is good” characters.
Jim, your post is right-on-the-facts, and yet there are alternative readings of Umair Haque's essay that (to my mind) are even more interesting and complexity-theoretic.
ReplyDeleteLet's consider the ansatz that trading abuses are not a cause of economic dysfunction, but rather a symptom of dysfunction. What might that dysfunction be?
It can't be a shortage of people … the world has plenty. It can't be a shortage of capital … the world has plenty. It can't be a shortage of demand … the world has plenty.
So perhaps the world is suffering from an acute shortage of enterprises, that put those people to work … by profitably investing that capital … to meet those demands.
Pursuant to this idea, as an exercise in complexity-theoretic enterprise design, I've been colliding NIH Director Francis Collins' recent Reengineering Translational Science: The Time Is Right (2011) with that oldie-but-goodie A Quantum Information Science and Technology Roadmap (QIST/LANL Report/LA-UR-02-6900, 2002).
The NIH Roadmap provides outstanding enterprise objectives, the QIST/LANL roadmap (when repurposed in light of subsequent QIT research) provides outstanding enterprise tools … and perhaps these two enterprise roadmaps together have the horsepower to pull us away from the black-hole of economic recession/depression.
This merged roadmap is a work-in-progress … perhaps I'll post a summary of it someday. Working out the various STEM details has been fun (and challenging), and for sure, the merged roadmap is a lot more optimistic than Umair Haque's economic scenario of "a burbling event horizon of a massive supergalactic black hole".
Context free languages aren't closed under intersection so there is no problem with the claim as clarified.
ReplyDeleteIndeed, since a prefix free set (or language if you prefer) can't be a homomorphic image of a non prefix free set the proof will have to go as follow:
Create two context free grammars whose resulting languages have an infinite prefix free intersection. Observe that every infinite set is the homomorphic image of an infinite prefix free set. Handle the finite cases by directly stuffing everything into the grammar.
The proof is (by now) standard:
ReplyDeletefix a Turing machine T that accepts the given r.e. (c.e.!) set
intersection of cfls can encode the language L of sequences of instantaneous descriptions of an accepting computation of T on input x [the language L consists of such computations for all x that are accepted]
use a homomorphism to erase everything but the input x for each string in L
While the readers of this blog are tolerant of unorthodox spellings, historians are not. If we are to interact with people in the humanities, we have to respect their culture. In the guest post there is a link for "Calender"
ReplyDeleteAccording to the OED, "calender" is either "one who calenders cloth" (wrings it between two rolling cylinders), or a "member of a mendicant order of dervishes in Turkey and Persia."
“Knowing some history is a good thing – Why?”
ReplyDeleteHere is hoping that John Sidles’ optimism is justified and that the powers to be can cobble together an economic game plan that avoids a double-dip recession.
The current mortgage mess may be a result in part of “lessons not learned” from the Savings and Loan crisis 20 years ago.
The unsettling thing about hedge funds is that they may be operating within the letter of the law and may be natural consequence of economic evolution – bigger (the amount of capital they can leverage), smarter (the algorithms they use for identifying opportunities), and streamlined management that makes them faster and more nimble than their prey -large banks, multi-national corporations and small countries.
It may take some forensic accountants teaming up with computer scientists to follow the money and figure out what is really happening.
Back to GASARCH’s more specific question:
Item 5: “Knowing something about the people can be interesting, but is likely less useful for research and teaching. If you disagree I would love to hear a respectful counterargument.”
I think GASARCH may have partially answered his own question in Item 3.
Students may benefit from a historic perspective and the views of the minority who challenge difficult and controversial ideas.
How many students of theoretical physicists know that Godel and Einstein had an intellectual disagreement over the possibility of a Unified Field Theory?
They were friends at the Institute for Advanced Studies at Princeton in spite of the fact they may have been polar opposites:
“Godel was cold and aloof, very serious, and suspicious of common sense. Einstein was warm and affable.” (Hawking’s “God Created the Integers” page 1261)
Although Godel did not agree with Einstein’s agenda; in a remarkable display of sheer intellect, Godel wrote a paper that “constructed a rotating model of the universe that satisfied Einstein’s equations”.
Uber techno-nerd Neil Stephenson's latest essay for the World Policy Institute, titled Innovation Starvation, is Stephenson's meditation upon many of the themes of this post.
ReplyDeleteAnon 10:19 and CSProf 4:23 are right, i'll just expand upon these:
ReplyDelete* CFLs can be recognized even in linear space (which is closed under intersection)
* let c_1, c_2, ..., c_n be configurations of a TM M; form a word c_1#rev(c_2)#c_3#rev(c_4)#... (where # is a delimiter and rev stands for reverse); we can easily check whether this encodes a computation of M using two (even deterministic) pushdown automata: one will check whether M can get from c_i to c_{i+1} for i odd, the other for i even
* corollaries: every r.e. language can be written as h(L1\cap L2) where L1 and L2 are dCFL, h is a homomorphism; the following problems are undecidable: given CFG G,G1,G2, is L(G1)\cap L(G2) empty? is L(G1)=L(G2)? is L(G1) subset of L(G2)? is complement of L(G) empty? is L(G) regular?
* btw, this [never heard of stuff] is taught to 2nd grade undergrad students on our university