La reducción usa el concepto de "historia computacional", es decir, una cadena que describa el proceso de computación global de una máquina de Turing, esta cadena podría describirse mediante una gramática libre del contexto.