מכונת טיורינג

הדמיה של מכונת טיורינג

מכונת טיורינגאנגלית: Turing machine) היא מודל חישובי מתמטי אשר באמצעותו ניתן לתאר באופן מופשט את פעולתו של מחשב (כולל מחשב מודרני).

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

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

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

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

Other Languages
Alemannisch: Turingmaschine
العربية: آلة تورنغ
беларуская: Машына Цьюрынга
беларуская (тарашкевіца)‎: Машына Т’юрынга
български: Машина на Тюринг
čeština: Turingův stroj
hrvatski: Turingov stroj
magyar: Turing-gép
interlingua: Machina de Turing
Bahasa Indonesia: Mesin Turing
Gĩkũyũ: Macini ya Turing
한국어: 튜링 기계
Lëtzebuergesch: Turingmaschinn
lietuvių: Tiuringo mašina
македонски: Тјурингова машина
Nederlands: Turingmachine
português: Máquina de Turing
română: Mașină Turing
srpskohrvatski / српскохрватски: Turingov stroj
Simple English: Turing machine
slovenčina: Turingov stroj
slovenščina: Turingov stroj
српски / srpski: Тјурингова машина
svenska: Turingmaskin
Türkçe: Turing makinesi
українська: Машина Тюрінга
Tiếng Việt: Máy Turing
中文: 图灵机
Bân-lâm-gú: Turing ki-hâi