Como pedías "el programa que me resuelva..." pues por eso preguntaba.
Porque si lo que quieres es una descripción de la máquina de Turing y cómo funciona, no tienes más que ir a Wikipedia o probar en cualquier buscador. Y por otra parte, si lo que quieres es un programa... al menos tendrás que definir algo más (o tu profesor). Si quieres una simulación, si lo que quieres es simular la máquina en sí, alguna programación particular, cualquier variante de las diversas que hay, etc, etc.
Porque la descripción en sí de la máquina es muy simple:
1. Una cinta infinita con casillas que contienen símbolos (para simplificar, ceros o unos).
2. Un 'puntero' o 'cabezal', que es capaz de:
2.1. desplazarse por la cinta hacia adelante y hacia atrás.
2.2. leer el contenido de la casilla que está señalando o escribirlo.
3. Una tabla de instrucciones que dicen qué operación debe hacer el cabezal (moverse, escribir, leer) según el estado en el que está y el símbolo de la casilla apuntada actualmente.
4. Un registro de estado, que guarda precisamente eso, el estado en el que está la máquina.
Y es que no tiene nada más en concreto. Bueno, sí, en general la tabla de instrucciones se suele definir por medio de 5-tuplas: (Ea, Sl, Se, M, Ep)
Ea: Estado actual
Sl: Símbolo leído
Se: Símbolo escrito
M: Movimiento, que puede ser una casilla a la derecha (R), una a la izquierda (L) o ninguno (N)
Ep: Estado próximo
(Aunque hay otras muchas variantes que usan 4-tuplas, 3-tuplas, 7-tuplas... o que usan símbolos diferentes u otras notaciones)
En fin, si quieres un simulador que te ayude a verlo mejor, no hay más que buscar un poco: http://ironphoenix.org/tril/tm/
(Aunque ten en cuenta que esta es una variante un poco más compleja con símbolos, no sólo 0 y 1)
Y si quieres tu programa en prolog, tampoco hace falta buscar mucho más allá:
http://www.cs.mu.oz.au/255/data/turing.pl
