In 1983, as a grad student, I knew that HALT \( \le_T \) KOLG but didn't know how to prove it. I asked around and A MONTH later through a series of connections I got the proof from Peter Gacs.
See here for the full story and see here for a write up of the proof
In 2023, as professor, I heard about a pennies-on-a-chessboard problem and wanted to know what was known about it. I blogged about it and AN HOUR later I found what I wanted.
See here for my blog post asking about and see here for my write up of all that's known.
Why the difference from a MONTH to an HOUR.
1) In 1983 there was no Google. I don't recall if there were other search engines, but even if there were there wasn't much to search. I do note that in 2023 Googling did not help me, though it may have helped my readers who pointed me to the information I wanted.
2) In 1983 email wasn't even that common. So the notion of just email such-and-such for the answer did not occur to me. (Also note that I am a last-blocker, see here.)
3) Here is a factor that should have been in my favor: the community of theorists was smaller so we kind of knew each other and knew who was doing what. AH- but who is this we ? I started at Harvard in 1980 but really only began doing theory in 1981 and didn't really know the players yet. However, I think the smallness of the community DID help Mihai Gereb (a grad student at Harvard) to know to contact Peter Gacs to help me find the proof. Contrast- today the community is so large that I might not know the players (I didn't for the penny-chess problem) though with email and the blog (next item) I can reach out to people who Do know the players.
4) The Blog- I have the ability to ASK several people at one time, and one of them might know. That worked in this case and in other cases, but it does not always work.
5) People without a blog can do something close to what I did- ask several people. And that can be more targeted. (ADDED LATER- a commenter pointed out that I should point out that Math Overflow and Stack exchange and sites like that are also options. Often when I Google a question I have been taken to those sites. I have had less luck asking them directly, but that could just be me.)
QUESTION: Is it easier to find things out NOW or 40 years ago? I think NOW by far, but I do see some possibly counterarguments. There is a balance- there were less places to look back then. Indeed, the answer to my question was NOT a journal article or a conference paper, it was another blog.
Lastly THANKS to my readers for pointing me to the sources I needed! Kudos!
ADDED LATER -a link to the Erdos-Guy paper that I need to put here to aid one of my comments is here
In your writeup for placing pennies, it seems that in the last figure (placement for n=7) p4 has the same distance to both p3,p6
ReplyDelete(This is Bill, I've hard problems having the comments say its me so in case I have that problem, you know its me.) I will fix this later but want to make an odd point now. Upon reading your comment I went to the paper of Erdos and Guy where I got this placement from. SURELY I misread or mistyped what they wrote. But it looks like (and again, I could still be WRONG) I transcribed what they said correctly, but its wrong. They had points
Delete(1,1), (1,3), (2,3), (3,7), (4,1), (6,6), (7,7).
And I've looked at mine many times since getting your comment to see where MY mistake was. Either
1) Erdos and Guy are WRONG. Unlikely
2) Your thinking its incorrect is WRONG. Unlikely.
3) I mis-transcribed it. Whle the most likely, I've checked it and can't find that I made a mistake (If you email me that I DID and what it WAS I will NOT be embarassed but I WILL fix it).
ANYWAY, I will find another placement and put it in later, but it bothers me that all 3 of the above options seem unlikely, yet one of them must be true.
The paper of Erdos and Guy is now linked to in this blog entry (putting links in comments does not seem to work).
MY BAD- my original grid was a 6x7 grid which caused the problem. For now I have left in my incorrect grid, labelled as such, and also added the correct one. THANKS for catching the error.
Delete... as you give answers to the simplest questions, those that remain unanswered are increasingly difficult
ReplyDeleteYou won't include MathOverflow / StackExchange network?
ReplyDeleteIt is really a new era, even as a "nobody" I usually get answers to (idiotic...) email questions from top notch people from 1/2 hour to 24h max.
ReplyDeleteIn the 80s we had libraries to find answers, or sometimes it was just easier to prove it ourselves. In the future we will have AI giving us answers in seconds instead of hours.
ReplyDeleteAbsolutely yes, if you're looking for a new approach to solve any given chess position.
DeleteAbsolutely no if you're asking for a novel (non-Euclidean) algorithm to compute say the GCD or a novel proof of the Pythagoras's theorem.
Small change, huge difference!
Infinitesimally few people care about better solutions to chess problems but all of us, living things, are constantly striving for improved approaches to solving real-world problems.
There was another source of information in 1983 that has been replaced. Back in 1983, institutions used to have technical report series and standard lists of libraries to which their TRs were sent automatically. When you made a TR you would give a list of individual recipients and postal addresses to send your hard copy of your TR to in addition to the standard list. (We didn't have MIME attachments or PDF. Postscript was new and created files too big to send.) Institutions would also publish lists of their TRs and you could request them to be sent to you. Since conference papers really were often "extended abstracts", these TRs were often the only long form versions of papers you had access to until the journal version came out. As a grad student I was lucky that either through faculty or the University of Toronto CS library, lots of these TRs were available to me, but if you weren't so connected you would miss out.
ReplyDeleteBy the end of the 1980's and early 1990's the culture of TRs had declined as people could begin to send papers as MIME attachments and TheoryNet could let people announce work, but there really wasn't a repository preprint culture to replace TRs until ECCC and arXiv.
Back in 1983, I used to check the CS library every month of so to see if there were any new TRs of interest that had arrived. Now we get daily updates in the theory blog aggregator (Theory of Computing Report) that have many times the number of new preprints I would see monthly.
When I search for an answer on stackoverflow the responses have a broad range of qualities that I am looking for and are not necessarily correlated to the ranking;
ReplyDeleteand these qualities are not specific to coding, they are equally applicable for any other real-world problem-solving situations.
a) Yea sure, this looks correct and I was going to do something similar this but the solution is not particularly concise (too many lines of code with multiple potential pitfalls that I need to verify carefully); these responses often ranked very high.
b) Ahh yes, look at that! This is how you'd do it. Now just a concise answer but reveals something new to me that I will make an effort to recall and reuse; these responses typically are ranked second high.
What appeals me with such answers is that it shows the creativity and ingenuity of the solution provider and intrinsically increases my confidence in the correctness of the solution; so I can afford to be tad less careful in verifying.
The responses to such comments are often very illuminating and highlight, contextualize and sometime simplify the original; this is what makes such responses 'special' so once again reinforcement by high-quality contributors.
c) Probably erroneous; ranked low and mostly ignored unless the top-ranked answers do not meet my requirements.
I will call it a win for AII if it can do a decent job at the above pretty well-defined task of grading stack-overflow responses without cheating (i.e., looking at the ranking of the commenters to the solutions etc).