"Gödel’s Doom" by George Zebrowski

First appeared in Popular Computing.  Reprinted by F&SF and Rudy Rucker.

Background:

Gödel's Incompleteness Theorem

Zebrowski's explanation:

"no machine-like entity that proceeds by clearly defined mechanical steps can complete any system that is rich enough to generate simple arithmetic--that is, make it a consistent system in which we could not come up with new, true, and still unproven propositions.  In fact, ones that would be unprovable in the system yet clearly true."

Summary:

Can a fast A.I. refute Gödel's theorem?  Felix and Bruno set to work to see if hard-deterministic universe or if free will is possible....

Spoiler / Commentary:

The A.I. achieves its aim, so they start it again.  In so doing, the A.I. erases its work and has launched them into a different universe--a free one, one that continually changes.

Felix and Bruno appeared in another story, "Sticky" and in "The Word Sweep", albeit probably in a different universe.