יום הולדת 100 לאלן טיורינג!

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

משפט רייס – הגרסה המלאה

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

הפוסט שיודע להדפיס את עצמו

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

על הבעייה הלא טריוויאלית של זיהוי תכונה לא טריוויאלית

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