מכונת טיורינג (Turing machine) היא רעיון לאופן פעולה של מחשב, שהציע אלן טיורינג בשנת 1936, עוד לפני המצאת המחשב עצמו. הוא ניסה אז להגדיר באופן מתמטי מהו אלגוריתם, "תהליך מכני".

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


הנה סרטון שמסביר את מכונת טיורינג ומדגים את הרעיון שלה:

http://youtu.be/1uDa7jkIztw


כך פועלת מכונת טיורינג:

http://youtu.be/mU8oiAbom0I


ודגם של המכונה שנבנה מלגו:

http://youtu.be/qc1C1Q0xFIM