یکی از دلایلی که میگیم مجموعه ماشین تورینگ روی یک الفبا شمارست اینه که میشه ماشین های تورینگ رو بایک و صفر کد کرد همانطور که بلدیم مجموعه *{۱و۰} شماراست پس نتیجه میشه مجموعه ماشین تورینگ شماراست!
ممکنه بعضی زبانها ماشین تورینگ نداشته باشند! مثالش تو لینز هست ولی این به شمارا بودن مجموعه ماشین های تورینگ رو زیر سوال نمیبره
(قضیه):به ازای هر سیگما غیر تهی زبانهایی هستند که شمارشی بازگشتی نیستند{یعنی تورینگ ندارند!})
مجموعه های نامتناهی میتونن شمارا باشند اگه بشه یه تناظری بین اونها و مجموعه اعداد طبیعی پیدا کرد
مثلن مجموعه اعداد طبیعی خودش نامتناهی هست ولی شماراست
مجموعه اعدا گویا شماراست یعنی میتونیم اعداد گویا مرتب کنیم از لحاظ ترتیب و مثلن بگیم دهمین عوض این مجموعه میشه چند
ماشین های تورینگ رو هم میشه پیدا کرد و تو یک مجموعه گذاشت بطوری که مرتب باشند تاکید کنم بعضی زبانها تورینگ ندارند ولی این به شمارا بودن لطمه نمیزنه
مثلن مجموعه اعداد طبیعی زوج با اینکه نسبت به مجموعه اعداد طبیعی برخی اعداد حذف شده ولی این قضیه شمارا بودن مجموعه اعداد طبیعی زوج رو نقض نمیکنه چون مثلن میشه تابع زیر رو براش تعریف کرد
f=1/2n هر عدد طبیعی زوج رو به مجموعه اعداد طبیعی نگاشت میکنه پس مجموعه اعداد زوج شماراست

(۱۰ دى ۱۳۹۱ ۰۹:۳۱ ب.ظ)هاتف نوشته شده توسط:  سلام
مجموئه ی همه ی ماشین های تورینگ روی یک الفبا، شمار است یا ناشمارا؟ لطفا استدلال کنید.
این سوال مربوط به کنکور مهندسی کامپیوتر سال ۸۰ بوده، تست شماره ۴۷

مجموعه ماشین های تورینگ روی یک الفا نامتناهی و شماراست.

نا متناهی بودن با شمارا و ناشمارا بودن فرق داره...