אלן טיורינג – הבדלי גרסאות

טיורינג פיתח את רעיון [[מכונת טיורינג]] באופן עצמאי, בניסיון לענות על שאלות העוסקות ב[[יסודות המתמטיקה]] שהועלו על ידי [[דויד הילברט]], ופרסם אותו באפריל [[1936]].{{הערה|A. M. Turing, [http://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf On computable numbers, with an application to the Entscheidungsproblem], Proceedings of the London Mathematical Society, 2 s. vol. 42 (1936–1937)‏}} המטרה הייתה ליצור הגדרה מתמטית מדויקת של [[אלגוריתם]] או "תהליך מכני". עוצמתו של הרעיון נעוצה בפשטות הקיצונית של ה[[מודל]] (בהשוואה למורכבותם של מחשבים אמיתיים). [[תזת צ'רץ'-טיורינג]] קובעת כי [[מכונת טיורינג]], חרף פשטותה, מסוגלת לבצע כל [[חישוב (מדעי המחשב)|חישוב]] או [[אלגוריתם]] שהוא בר-ביצוע במחשב כלשהו. מבחינה זו, מכונת טיורינג שקולה לכל מחשב, ולכן משמשת עד היום ב[[מדעי המחשב]], בעיקר ב[[תורת הסיבוכיות]] ובתורת ה[[חישוביות]], כבסיס לחקר יכולותיו ומגבלותיו של המחשב (מחשב כלשהו, תוך התעלמות מתכונותיו של מחשב מסוים זה או אחר).