Hola! Un posible algoritmo para resolver este problema es el siguiente:
Para cada símbolo 0 ó 1, se lee de la cadena de entrada colocada en la cinta, y se busca si existe otro 0 ó 1 en correspondencia. Si es así, se reemplazan ambos símbolos con otro símbolo de modo que los símbolos para los que ya se ha encontrado correspondencia se ignorarán en los siguientes pasos.
Si en la búsqueda no se encuentra correspondencia (se llega al final de la cadena sin encontrar el mismo símbolo, esto significa que no hay igual número de ceros que de unos) entonces se rechaza la cadena (no se acepta).
Si todos los 0s y 1s acaban en correspondencia la cadena se acepta.
La máquina sería esta (donde q es el estado inicial, R el estado de rechazo o no aceptación y F el estado de aceptación):
Ejemplos
Entrada: 001
Operación de la máquina:
q Δ001 ⊢ ΔA001 ⊢ ΔxC01 ⊢ Δx0C1 ⊢ ΔxD0x ⊢ ΔDx0x ⊢ DΔx0x ⊢ ΔEx0x ⊢ ΔxE0x ⊢ ΔxxCx ⊢ ΔxxxCΔ ⊢ R (reject)
Entrada: 0101
Operación de la máquina:
q Δ0011 ⊢ ΔA0101 ⊢ ΔxC101 ⊢ ΔDxx01 ⊢ DΔxx01 ⊢ ΔExx01 ⊢ ΔxEx01 ⊢ ΔxxE01 ⊢ ΔxxxC1 ⊢ ΔxxDxx ⊢ ΔxDxxx ⊢ ΔDxxxx ⊢ DΔxxxx ⊢ ΔExxxx ⊢ ΔxExxx ⊢ ΔxxExx ⊢ ΔxxxEx ⊢ ΔxxxxEΔ ⊢ F (accept)