For each input, I, we specify a Boolean expression which is satisfiable if and only if the machine M accepts I. The Boolean expression uses the variables set out in the following table.
Για κάθε εισαγωγή, I , εμείς προσδιορίζουμε μια έκφραση Boolean η οποία είναι ικανοποιητική αν και μόνο αν η μηχανή M δέχεται την Ι. Η έκφραση Boolean χρησιμοποιεί τις μεταβλητές που ορίζονται στον ακόλουθο πίνακα.