Türinq maşınları sonlu avtomatlar/sonlu dövlət maşınlarına bənzəyir, lakin məhdud yaddaşın üstünlüyünə malikdir … Onlar ümumi kompüterləri simulyasiya etmək qabiliyyətinə malikdirlər; ümumi kompüterin həll edə biləcəyi problem (kifayət qədər yaddaş verildikdə) Turing maşını ilə də həll edilə bilər və əksinə.
RAM ilə TM arasındakı fərq nədir?
Türinq maşını bacarmaz RAM maşını O(1)-də hesab edə bilər (müəyyən məhdudiyyətlər altında). Turing maşını edə bilməz. Turing maşınları RAM maşınlarını polinom şəkildə simulyasiya edir, yəni bəzi sabit c üçün O(nk) vaxtında işləyən istənilən RAM maşını O(nck) vaxtında işləyən Turing maşını ilə simulyasiya edilə bilər.
Türinq maşınının lenti sərhədsizdir?
Türinq maşını (TM) iki yaddaşdan ibarət vəziyyət maşınıdır: məhdud lent və sonlu vəziyyətə nəzarət cədvəli. Lent məlumatları simvol kimi saxlayır. Maşının lentdə çox kiçik düzgün əməliyyatlar dəsti var, ümumilikdə 6 (oxumaq, yazmaq, sola köçürmək, sağa hərəkət etmək, vəziyyəti dəyişmək, dayandırmaq).
Türinq maşını niyə güclüdür?
Türinq maşınları nə qədər güclüdür? Turing maşınları istənilən normal və ya kontekstsiz dili qəbul edə bilər. Türinq maşınları əsas arifmetik hesablamaları yerinə yetirə bilir … Türinq tezisində deyilir ki, “mexaniki vasitələrlə” həyata keçirilə bilən hər hansı hesablama Türinq maşını ilə həyata keçirilə bilər (səmərəlilik məsələlərinə məhəl qoymayaraq).
Türinq maşınları əbədi olaraq dönə bilərmi?
turing(turingDescrip) nə dayana, nə də əbədi dönə bilər; bunun heç bir mənası yoxdur.
