Interpretation of if $\cdots$ then in terms of a turing machine (or a general recursive function)

Question

I am trying to understand various commands in high level programming in terms of turing machines (i.e. computable functions). For eg for/while loops can be though as recursion of a specific function. The only problem I face is I cannot seem to interpret if $\cdots $ else as a recursion function? Any leads would be much appreciated.

Answer 1

In the Turing machine framework, case branching is handled by the state transition system: at an atomic level the Turing machine can decide which state to move into based on the content of the cell currently examined, and with some tedium we can reduce complicated questions to checking individual (carefully prepared) cells.

---

In the approach via $\mu$-recursion, we have instead a simple algebraic trick we can use. Suppose I have a computable predicate $P$ and computable functions $f,g$, and I want to define a computable function $s$ such that $s(x)=f(x)$ if $P(x)$ and $s(x)=g(x)$ if $\neg P(x)$.

Since $P$ is computable, its characteristic function $p$ is also computable. We can now define $s$ as a simple combination of $f,g$, and $p$: $$s(x)=p(x)f(x)+(1-p(x))g(x).$$

No need to even use minimization here!

Similarly, suppose we have two computable predicates $P,Q$ and computable functions $f,g,h$, and we want $s(x)=f(x)$ if $P(x)$, $s(x)=g(x)$ if $\neg P(x)$ but $Q(x)$, and $s(x)=h(x)$ if $\neg P(x)$ and $\neg Q(x)$. Letting $p,q$ be the computable characteristic functions of $P,Q$, we get $$s(x)=p(x)f(x)+(1-p(x))(q(x))g(x)+(1-p(x))(1-q(x))h(x).$$

Answer 2

Suppose we have a decidable predicate $T$ and two computable functions $P, Q$.

We want to construct a Turing Machine which computes $P(x)$ if $T(x)$, otherwise computes $Q(x)$.

To do so, we specify the following two-tape Turing machine. As usual, in the beginning, the first tape holds the input, and the second tape is initially empty.

First, we copy the contents of the first tape onto the second tape.

Then, we run a 1-tape Turing machine that computes $T$ on the second tape.

If the result on the second tape is $true$, we run the 1-tape machine that computes $P$ on the first tape. Otherwise, we run the 1-tape machine that computes $P$ on the first tape.

This gives us a 2-tape machine that computes $P(x)$ if $T(x)$, otherwise computes $Q(x)$. And any 2-tape machine can be converted into an equivalent 1-tape machine.