A related example that I, personally, considered science fiction back in the 80s: Jerry Pournelle's prediction that by the year 2000 you'd be able to ask a computer any question, and if there was a humanly-known answer, get it back. Google arrived with a couple years to spare. To me that had sounded like an AI-complete problem even were all the info online.