Uma das principais ferramentas de uma Máquina de Turing, que possibilita que seu poder de computação seja maior do que de outros modelos mais simples, é uma fita infinita, dividida em células, onde informações de um alfabeto ficam armazenadas.

Uma Máquina Dobradora é uma máquina inspirada na Máquina de Turing, onde a fita é finita, os dados armazenados são números inteiros e, ao invés do mecanismo de funcionamento tradicional de Turing, a máquina utiliza operações de dobras da fita para fazer computações.

Para efetuar uma dobra, a máquina escolhe uma posição entre células adjacentes e, ao realizar a dobra, ela soma os valores das células que se sobrepuseram, como pode ser visto na figura abaixo.

Observe também que a dobra pode ser feita em uma posição anterior ao centro da fita, como ilustrado a seguir. Note também que, com isso, podem ser feitas dobras também no início e no final da fita, invertendo a ordem desta.

A empresa Science of Bends Company vem desenvolvendo versões comerciais da Máquina Dobradora e a produção tem aumentado recentemente. Infelizmente o último lote de Máquinas Dobradoras produzidas está com problemas e algumas máquinas não estão funcionando corretamente. Assim, testes são necessários para evitar a venda de produtos com defeito, o que poderia denegrir a imagem da empresa.

Para testar as máquinas, um conjunto de testes é dado e, para cada fita, a máquina devolve o resultado da computação. Assim os engenheiros responsáveis pelos testes tomam nota do resultado e podem verificar se este está correto. Mas os engenheiros esqueceram-se de tomar nota de qual computa ção foi feita em cada conjunto de teste. Para evitar a necessidade de testar todas as máquinas novamente, os engenheiros estariam satisfeitos em descobrir se pelo menos existe uma sequência de dobras coerente para um par de fitas de entrada e saída. Para isso, eles contrataram você para desenvolver um programa que verifique, para cada fita de entrada, se existe uma sequência de dobraduras que leve a uma fita de saída.