not just a matter of time, &c

[Joao Marcos]

Alguns artigos de divulgação recentes, escritos por Ken Wessen para a
+plus Magazine:

* * *

Not just a matter of time: Measuring complexity
https://plus.maths.org/content/not-just-matter-time-part-1

"As computers are constantly becoming faster and better, many
computational problems that were previously out of reach have now
become accessible. But is this trend going to continue forever, or are
there problems computers will never, ever be able to solve? Let's
start our consideration of this question by looking at how computer
scientists measure and classify the complexity of computational
algorithms."

* * *

Not just a matter of time: The halting problem
https://plus.maths.org/content/not-just-matter-time-part-ii

* * *

Not just a matter of time: The busy beaver
https://plus.maths.org/content/not-just-matter-time-part-iii

"In a previous article we saw that writing the HALT program is a
logical impossibility, but what about more straightforward calculating
tasks? Our simple computing model has stood up to the challenge of the
hyper-exponential growth generated by the ultra-recursive Ackermann
function. But how will it go playing the Busy Beaver game, invented by
Tibor Radó in 1962?"

* * *

Ping pong balls, infinity and superpowers
https://plus.maths.org/content/ping-pong-balls-and-super-powers

* * *