Turing machine

מכונת טיורינג (שמה של מכונה תיאורטית (אוטומט) המסוגל לפעולות קלט/פלט פשוטות בה משתמשים להוכחות מתמטיות)

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

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


   רוצים לדעת עוד?