החקירה לגבי האם כל הווריאציות השונות של מכונות טיורינג שוות ערך ביכולת המחשוב היא שאלה בסיסית בתחום של מדעי המחשב התיאורטיים, במיוחד במחקר של תיאוריית המורכבות החישובית וההכרעה. כדי להתמודד עם זה, חיוני לשקול את האופי של מכונות טיורינג ואת הרעיון של שקילות חישובית.