ما هي الظاهرة التي كانت في معظمها أقل تأثيراً من اختراع آلة تورينج؟ ،
قبل أن يبدأ البحث الفعلي المكرس بشكل صريح لتعقيد المشاكل الخوارزمية ، تم وضع العديد من الأسس من قبل مختلف الباحثين. كان الأكثر تأثيراً بين هذه هو تعريف آلة تورينج بواسطة آلان تورينج في عام 1936 ، والذي تبين أنه تبسيط قوي ومرن جدًا للكمبيوتر.