Il programma deve contenere almeno due classi, una per disegnare l'interfaccia e una per gestire gli eventi. La prima contiene il metodo main(), la seconda il metodo actionPerformed(). L'istruzione di stampa va nella seconda.

Il primo passo è rappresentare il dato di input, che è un numero compreso fra zero e sette. Servono quindi tre bit di ingresso, indicati per esempio con a, b, e c. L'uscita è un singolo bit.

L'uscita u vale 1 quando i tre ingressi rappresentano i valori 0, 3 oppure 6. Questi valori in binario sono a=0, b=0, c=0 per zero, a=0, b=1, c=1 per tre e a=1, b=1, c=0 per sei. In tutti gli altri casi l'uscita vale zero.

insieme dei nodi e degli archi

{1,2,3,4,5}, {(3,1), (5,4), (5,2), (2,5)}}

insiemi di successori

per ogni nodo contiene l'insieme dei suoi successori
{1,2,3,4,5}, {(1,{}), (2,{5}), (3,{1}), (4,{}), (5,{2,4})}

matrice di adiacenza

ogni cella indica se esiste un arco fra un nodo e l'altro

	1	2	3	4	5
1	False	False	False	False	False
2	False	False	False	False	True
3	True	False	False	False	False
4	False	False	False	False	False
5	False	True	False	True	False

Le stringhe accettate sono solo quelle che iniziano e finiscono con a, quella che iniziano e finiscono con b e quelle che iniziano e finiscono con c. I caratteri in mezzo sono tutti tranne a.

a[^a]*a|b[^a]*b|c[^a]*c

I problemi indecidibili sono quelli che non solo risolubili da nessun algoritmo. Quelli intrattabili non sono risolubili da un algoritmo che impiega tempo polinomiale.

Non esiste quindi nessun problema indecidibile che sia trattabile, perche' sarebbe un problema che al tempo stesso ha un algoritmo risolutivo che impiega tempo polinomiale ma non ha nessun algoritmo risolutivo.

Al contrario, esistono numerosi problemi che hanno algoritmi risolutivi ma nessuno di questi impiega tempo polinomiale. Un esempio è il problema dei ciottoli, quello di verificare l'esistenza di una strategia vincente. Questo problema è infatti risolubile, ma solo da algoritmi che impiegano tempo esponenziale e quindi non polinomiale.