yo lo veo algo así:

está demostrado que se tiene el mismo poder de cómputo una máquina que sólo usa 0 (blancos) y 1 (puntitos), así que usamos eso

la configuración actual de una máquina de turing se puede representar como:
s - el símbolo al que mira el cabezal
e - el estado actual
l - la parte de la cinta a la izquierda del cabezal (como son 0 y 1, es un número en binario)
r - idem pero derecha (sería la representación binaria invertida)

esto se puede representar de forma única como un natural C:
C = 2^s 3^e 5^l 7^r

notar que se puede recuperar el símbolo s de una config haciendo log(2, C),
análogo para los otros (log es FR)

la máquina de turing en sí se puede representar de la forma
a10, q10, a11, q11, a20, q20, ..., ak0, qk0, ak1, qk1 (k estados)

donde:
ais es la accion cuando en el estado i veo al simbolo s:
- 0 para escribir 0, 1 para el 1, 2 para moverme a la derecha, 3 para moverme a la izq
qis el nuevo estado para ir cuando estoy en el estado i y veo el simbolo s

entonces podemos codificar a la maquina de turing M como un natural:
M = 2^a10 3^q10 ...

la función que nos dice el n-ésimo primo es FR, y por lo tanto podemos recuperar el exponente con composicion FR

despues hay que definir funciones FR que modifiquen la configuracion dependiendo de la máquina
por ejemplo, nuevaizquierda(l,r,s,a=3) = 2*l + s (cuando me muevo a la izquierda)

y una funcion componiendo las anteriores conf(M, X, t) que me diga la configuracion después de t pasos con una cinta X

despues una funcion done(M,X,t) que me diga si termine en el estado 0 (si estoy en otro, no haltié)
para eso se fija el estado de conf(M, X, t)

con eso, podes usar un minimizador en done(M,X,t) para averiguar cuantos pasos necesitas para haltear
(puede ser que no termine, es parcial)

despues usas la funcion conf en esa cantidad de pasos, y te queda la configuracion de la cinta como tupla (s,e=0,l,r)
asi que la funcion FR final te quedaria algo de la onda

f(M, X) = construir_cinta( conf(M, X, minimizador_t( !done(M,X,t) ) )