Da bismo odgovorili na pitanje može li Turingov prepoznatljiv jezik tvoriti podskup jezika koji se može odlučiti, bitno je razmotriti temeljne koncepte teorije računalne složenosti, posebno se fokusirajući na klasifikacije jezika temeljene na njihovoj mogućnosti odlučivanja i prepoznatljivosti. U teoriji računalne složenosti, jezici su skupovi nizova preko neke abecede,