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