سلام
مجموئه ی همه ی ماشین های تورینگ روی یک الفبا، شمار است یا ناشمارا؟ لطفا استدلال کنید.
این سوال مربوط به کنکور مهندسی کامپیوتر سال ۸۰ بوده، تست شماره ۴۷
(۱۰ دى ۱۳۹۱ ۰۹:۳۱ ب.ظ)هاتف نوشته شده توسط: سلام
مجموئه ی همه ی ماشین های تورینگ روی یک الفبا، شمار است یا ناشمارا؟ لطفا استدلال کنید.
این سوال مربوط به کنکور مهندسی کامپیوتر سال ۸۰ بوده، تست شماره ۴۷
مجموعه ماشین های تورینگ روی یک الفا نامتناهی و شماراست.
نا متناهی بودن با شمارا و ناشمارا بودن فرق داره...
(۱۱ دى ۱۳۹۱ ۰۲:۲۷ ب.ظ)cpt.mazi نوشته شده توسط: مجموعه ماشین های تورینگ روی یک الفا نامتناهی و شماراست.پس روی یک الفبا هم شماراست هم نامتناهی؟!
(۱۱ دى ۱۳۹۱ ۰۲:۲۷ ب.ظ)cpt.mazi نوشته شده توسط: نا متناهی بودن با شمارا و ناشمارا بودن فرق داره...بله این واضحه، مثلا مجموئه اعداد طبیعی شمارای نامتنهای است. چرا این رو گفتید؟
(۱۱ دى ۱۳۹۱ ۰۴:۱۶ ب.ظ)هاتف نوشته شده توسط:(11 دى ۱۳۹۱ ۰۲:۲۷ ب.ظ)cpt.mazi نوشته شده توسط: مجموعه ماشین های تورینگ روی یک الفا نامتناهی و شماراست.پس روی یک الفبا هم شماراست هم نامتناهی؟!
(۱۱ دى ۱۳۹۱ ۰۲:۲۷ ب.ظ)cpt.mazi نوشته شده توسط: نا متناهی بودن با شمارا و ناشمارا بودن فرق داره...بله این واضحه، مثلا مجموئه اعداد طبیعی شمارای نامتنهای است. چرا این رو گفتید؟
آره ، هم شماراست و هم نا متنهایی. علت نامتناهی بودنش که سادست ، یعنی میشه به تعدا نا متناهی ماشین تورینگ براش طراحی کرد. اما شمارا بودنش بخاطر اینه که میشه ماشین های تورینگ ساخته شده رو با یک تناظر یک به یک به اعداد طبیعی نگاشت کرد.
در رابطه با اینکه گفتم ناشمارا و شمارا با متناهی و نا متناهی فرق داره فکر کردم شما اشتباه کردید و اینو نمیدونستید.ببخشید...
یکی از دلایلی که میگیم مجموعه ماشین تورینگ روی یک الفبا شمارست اینه که میشه ماشین های تورینگ رو بایک و صفر کد کرد همانطور که بلدیم مجموعه *{۱و۰} شماراست پس نتیجه میشه مجموعه ماشین تورینگ شماراست!
ممکنه بعضی زبانها ماشین تورینگ نداشته باشند! مثالش تو لینز هست ولی این به شمارا بودن مجموعه ماشین های تورینگ رو زیر سوال نمیبره
(قضیه):به ازای هر سیگما غیر تهی زبانهایی هستند که شمارشی بازگشتی نیستند{یعنی تورینگ ندارند!})
مجموعه های نامتناهی میتونن شمارا باشند اگه بشه یه تناظری بین اونها و مجموعه اعداد طبیعی پیدا کرد
مثلن مجموعه اعداد طبیعی خودش نامتناهی هست ولی شماراست
مجموعه اعدا گویا شماراست یعنی میتونیم اعداد گویا مرتب کنیم از لحاظ ترتیب و مثلن بگیم دهمین عوض این مجموعه میشه چند
ماشین های تورینگ رو هم میشه پیدا کرد و تو یک مجموعه گذاشت بطوری که مرتب باشند تاکید کنم بعضی زبانها تورینگ ندارند ولی این به شمارا بودن لطمه نمیزنه
مثلن مجموعه اعداد طبیعی زوج با اینکه نسبت به مجموعه اعداد طبیعی برخی اعداد حذف شده ولی این قضیه شمارا بودن مجموعه اعداد طبیعی زوج رو نقض نمیکنه چون مثلن میشه تابع زیر رو براش تعریف کرد
f=1/2n هر عدد طبیعی زوج رو به مجموعه اعداد طبیعی نگاشت میکنه پس مجموعه اعداد زوج شماراست