מבחן טיורינג

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

הבעיה העשירית של הילברט – איך מקודדים דיופנטית את כל הסדרות הסופיות?

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

משפט השאריות הסיני

בית הספר "הר סיני" החליט להתעלל בשכבת כיתה י' שלו ולארגן מהם קבוצות למשחק כדור זה או אחר. ראשית לקח בית הספר את כלל תלמידי השכבה והחל לחלק אותם לקבוצות כדורגל (11 שחקנים בקבוצה) אבל לרוע המזל התברר שנותר תלמיד … להמשיך לקרוא

הבעיה העשירית של הילברט – פונקציות דיופנטיות וחיות אחרות (רקורסיביות)

אנו ממשיכים בדרך שלנו אל ההוכחה שלא קיים אלגוריתם שפותר את הבעיה העשירית של הילברט. אני מניח שקראתם את פוסט המבוא ולכן קופץ ישר לעניינים הפעם. המושג המרכזי בפוסט הקודם היה קבוצה דיופנטית. זוהי קבוצה $latex S=\left\{ \left(a_{1},\dots,a_{n}\right)\right\} $ של … להמשיך לקרוא