Turning a Biased Coin into an Unbiased one Deterministically Non-deterministic Exact Algorithm
There is a simple algorithm to turn a biased coin into a fair one: 


*

*Flip the coin twice.

*Identify HT with H and TH with T.

*Discard cases HH and TT.


This algorithm produces a perfectly fair coin, but it is non-deterministic.
Deterministic Approximation
I also know it is possible to approximate a fair coin with a deterministic algorithm:
Let $C_0$ be the biased coin and define $C_1$ by flipping $C_0$ twice. $C_1$ is H if $C_0$ was HH or TT, and $C_1$ is T if $C_0$ was HT or TH.
We can see that if the probability that $C_0$ was heads is $p$, then the probability that $C_1$ is heads is $p_1 = 1 - 2p(1 - p)$. This is a parabola connecting $(0,1), (.5,.5)$, and $(1,1)$ and we can see that if we assume $0<p<1$ then the function has a fixed point at $0.5$. Since $0.5 < p_1 < p$ if $p>0.5$ and $0.5<p_1<1$ if $p<0.5$, then we can see that a fixed point iteration with $0<p<1$ will always converge to $0.5$. Therefore, we can find a deterministic $C_i$ that is arbitrarily fair (defined by flipping $C_{i-1}$ twice).
My Problem
I am trying to find out if, given some biased coin with rational probability of heads $p$, we can construct an algorithm to solve this problem that is both deterministic and exact. Does anyone have any insights?
(Note that the algorithm only has to work for a fixed probability $p$, since as pointed out in the comments and answer, there are some $p$, e.g., $p = 1/3$ for which there is no such algorithm.)
 A: An algorithm that works for any $p$ doesn't exist. It is possible to solve the problem for some $p$.
Let $p$ be the probability of heads.
Consider a deterministic algorithm $F$ which uses $n$ tosses. Denote $A$ the set of all possible sequences of $n$ coin tosses ($|A| = 2^n$). The $F$ is essentially a function $F: A \to \{0, 1\}$, which returns 0 (heads) for some sequences of $n$ tosses, and 1 (tails) for the rest.
Our deterministic algorithm defines two sets, $H = \{v \in A | F(v) = 0\}$ - the set of $n$-toss sequences where out algorithm decided heads, and $T = A \setminus H$, such that $\mathbb{P}[H] = \mathbb{P}[T] = 0.5$.
On the other hand, for any sequence $v \in A$ denote $h(v)$ be the number of tails in $v$.
$$\mathbb{P}[H] = \sum_{v \in H}\mathbb{P}[v] = \sum_{v \in H} p^{h(v)}(1-p)^{n - h(v)} {\hspace{2cm}} [1]$$
We need to make this $\frac{1}{2}$.
Let $p = \frac{r}{q}$ when fully reduced. Then
$$p^{h(v)}(1-p)^{n - h(v)} = \frac{r^{h(v)}(q-r)^{n-h(v)}}{q^n}$$
Let's count how many times each possible value of $h(v)$ appears in the sum [1]:
Denote $c_k = |\{v | v \in H \text{ and } h(v)=k \}|$. Then [1] becomes
$$\mathbb{P}[H] = \sum_{k=0}^n c_k \frac{r^{k}(q-r)^{n-k}}{q^n} =
\frac{\sum_{k=0}^n c_k r^{k}(q-r)^{n-k}}{q^n} = \frac{1}{2}$$
An algorithm that works for all $p$ doesn't exist, because if $q$ is odd, there is no way to introduce a factor of $2$ in the denominator of this expression. The best we can do is, given a $p$, try to find an algorithm that works for that specific $p$, or determine that such doesn't exist.
Since there are $n \choose k$ sequences of coin tosses with length $n$ and $k$ heads, we also need $c_k \leq {n \choose k}$.
If $q$ is even, and we have a solution to the following equation, satisfying the bounds on $c_k$
$$\sum_{k=0}^n c_k r^{k}(q-r)^{n-k} = \frac{q^n}{2}$$
Then we can simply include $c_k$ sequences containing $k$ heads in $H$ for each $k$ to get our algorithm.
Note that this equation has finitely many potential solutions, so we can simply try them all.
