Vaqt va makonning ma'lum miqdorini qo'llash bilan muammoni hal qilish nimani anglatishini aniq aniqlash uchun aniq Turing mashinasi kabi hisoblash modelidan foydalanamiz. Turingning aniqlangan mashinasi M ning x kirishida talab qiladigan vaqt, mashinaning to'xtashi va javob berishdan ('ha' yoki 'yo'q') oldin amalga oshiradigan holat o'tishlarining yoki harakatlarining umumiy sonidir. Turing mashinasi M, agar M ning har bir n uzunlikdagi kirishida talab qilinadigan vaqt f (n) dan oshmasa, f (n) vaqt davomida ishlaydi deb aytiladi. Agar f (n) vaqt ichida ishlaydigan Turing mashinasi mavjud bo'lsa, A ni hal qilish vazifasi f (n) vaqt ichida hal qilinishi mumkin. Murakkablik nazariyasi vazifalarni murakkabligi asosida tasniflashga qiziqqanligi sababli, u ba'zi mezonlar asosida vazifalar to'plamini belgilaydi. Masalan, determinantli Turing mashinasida f (n) vaqt davomida yechiladigan vazifalar to'plami keyinchalik DTIME (f (n)) deb ataladi.
Turingning aniqlangan mashinasida javobni topish uchun kerak bo'lgan vaqt nima sifatida ifodalanadi?
holat o'tishlarining