Looking for a short science fiction story about a computer defeated by a paradox?

Question

This is a short science fiction story about a computer that is put out of action by being presented with a paradox. The computer runs a space station on a distant planet and is supposedly failsafe. A visitor makes a bet that he can bring the computer to a standstill. He does this by giving it a paradox. The computer shuts down in order to concentrate on the insoluble paradox.

Answer 1

"The Monkey Wrench" by Gordon Dickson, first published in Astounding Science Fiction, August 1951, available at the Internet Archive. From Wikipedia:

In this story, Lowland society lawyer Cary Harmon drops in unannounced on the weather station of meteorologist Burke McIntyre, high in the Lonesome Mountains, a jagged chain of the deserted shorelands of Venus's Northern Sea. Curious about Burke's hermit's existence, Cary queries to gain knowledge of how Burke works. The Brain, a newly installed computer, does all observations, and Burke, by himself, just sits at the desk and prepares weather data for transmission to the Weather Center down at the Capital City.

Cary tries to find fault in the machine, but Burke proudly argues that the Brain, "A big tin god", is invulnerable, that it can never break down. Along the debate, Burke claims that any bank out of the twenty could handle any situation, and if a situation too big for one to handle arose, it just hooked in with one or more of the idle banks until it was capable of dealing with the situation.

Theoretically, it's possible for the machine to bump into a problem that would require all or more than all of its banks to handle. For example, if this station suddenly popped into the air and started to fly away for no discernible reason, the bank that first felt the situation would keep reaching out for help until all the banks were engaged in considering it, until it crowded out all the other functions the machine performs. But even then, it wouldn't overload and burn out. The banks would just go on to considering the problem until they had evolved a theory that explained why we were flying through the air and what to do about returning us to our proper place and functions.

Despite that, Cary happily makes a bet that he could gimmick the machine in one minute. He successfully does so by throwing at the machine a metaphoric monkey wrench - a paradox:

You must reject the statement I am now making to you, because all the statements I make are incorrect.

With the Brain dedicating all of its banks to working on the paradox, the consequence of Cary's action finally bears down upon the pair, as the harsh negative temperatures of Venus rapidly sets in.