In 1984, TIME magazine quoted the chief editor of a certain software publication as saying: "Put the right kind of software into a computer, and it will do whatever you want it to. There may be limits on what you can do with the machines themselves, but there are no limits on what you can do with software." This talk will survey results obtained over the last 80 years by mathematicians, logicians and computer scientists, which disprove this ignorance-based statement in a sweeping and fundamental way. We shall discuss problems that are provably non-computable, as well as ones that are hopelessly time- or memory-consuming (requiring far more time than has elapsed since the Big Bang, or requiring a computer would not fit into the entire known universe). Time permitting, we will also take a somewhat more amusing look at these facts, and relate them to the (im)possibilities of true artificial intelligence. The topic is very closely linked to some of Alan M. Turing’s most important work.
Mot(s) clés libre(s) : computer