Obtaining irrational probabilities from fair coins?

Suppose I have access to a fair coin. Is it possible to come up with a procedure that (1) returns TRUE with irrational probability (say $1/\sqrt{2}$) and FALSE otherwise, and (2) terminates in a finite amount of time?

I would think not, because at the end of the day I'm just assigning either TRUE or FALSE to sequences of coin flips, and any such assignment results in a rational probability. However, I don't think there's harm in asking: is there some extraordinarily clever way to extract irrational probabilities?

[Edit] Alternatively, what if we relax condition (2) to "terminates with probability 1"? (Thanks user6312!)

Solution 1:

It depends on what you mean by "terminates in a finite amount of time". This could mean:

1. Always terminates in a finite amount of time, or

2. Terminates in a finite amount of time with probability 1.

If you mean the former, you are correct that any event that depends on finitely many coin flips will have rational probability.

However, if you allow processes that terminate with probability 1, then any irrational probability is possible. For example, if you want an event with probability $1/\sqrt{2}$, simply interpret the sequence of coin flips as the digits of a binary number between 0 and 1, and check whether the resulting number is less than $1/\sqrt{2}$. With probability 1, you will be able to tell after some finite number of flips whether or not your number is less than $1/\sqrt{2}$, so you will almost surely have to flip only a finite number of coints.

Solution 2:

Flip the coin until you get a tail. If the number of heads is prime, return TRUE. Otherwise, return FALSE.