(1) Una màquina de Turing amb un petit nombre d'Estats que s'atura quan va començar amb una cinta en blanc, però escriu un gran nombre de no buits o pren un gran nombre de passos. (2) El problema de trobar el nombre màxim de no buits han escrit o mesures adoptades per les màquines de Turing amb un determinat nombre d'Estats i símbols.