این مسئله در ارتباط با ماشین‌های تورینگ است. با این ماشین‌ها در آزمون‌های گذشته آشنا شده‌اید. در صورتی که تعریف ماشین تورینگ را به خاطر ندارید، به انتهای این مسئله مراجعه کنید.

مسئله به این صورت است: فرض کنید که در ابتدا در خانه‌های 0 تا $k-1$ حافظه، یک دنباله از رقم‌های 0 و ۱ و در خانه‌های $k+1$ تا $2k$ دنباله‌ای دیگر از رقم‌های 0 و ۱ نوشته شده است که به ترتیب بسط دودویی عددهای $A$ و $B$ را مشخص می‌کنند. در بقیه‌ی خانه‌های حافظه نیز در ابتدا عدد ۲ قرار گرفته است. همچنین فرض کنید که حق نداریم رقمی به‌جز 0 و ۱ و ۲ درهیچ‌یک ازخانه‌های حافظه بنویسیم. برنامه‌ای بنویسید که به صورتی عمل کند که پس از اجرای آن و متوقف شدن ماشین، در خانه‌های 0 تا $k-1$، $k+1$ تا $2k$ و $2k+2$ تا $3k+2$ به ترتیب بسط دودویی عددهای $A$، $B$ و $A+B$ نوشته شده باشد و در بقیه‌ی خانه‌ها رقم ۲ قرار گرفته باشد.

برای مثال اگر وضعیت حافظه در ابتدا به صورت زیر باشد:

پس از اجرای برنامه باید به صورت زیر درآید:

تعریف ماشین تورینگ: یک ماشین تورینگ به این صورت تعریف می‌شود: ماشین دارای یک نوار حافظه‌ی نامتناهی است که با شماره‌های $...,-2,-1,0,1,2,…$ مشخص می‌شوند. در هر یک از خانه‌های این حافظه، می‌توان یکی از رقم‌های ۰ تا ۹ را ذخیره کرد. یک هد در هر لحظه روی یکی از خانه‌های این نوار قرار گرفته است. ماشین تنها می‌تواند عدد ذخیره شده در خانه‌ای را بخواند که هد روی آن قرار دارد و یک عدد جدید در آن خانه بنویسد. ماشین در هر لحظه، در یک «حالت» قرار دارد. حالت‌های این ماشین را با $S_0,S_1,S_2,…$ نشان می‌دهیم. در ابتدا ماشین در حالت $S_0$ است و هد روی خانه‌ی صفر نوار حافظه قرار دارد. پس از این، ماشین بر اساس یک «برنامه» که برای آن نوشته شده است، عمل می‌کند. برنامه از تعداد متناهی «دستور» تشکیل شده است. البته ترتیب دستورات برنامه مهم نیست. هر یک از دستورات برنامه به شکل $(S_i,\alpha) \rightarrow (S_j,\beta,x)$ است که در آن $S_i$ و $S_j$ متعلق به مجموعه‌ی حالت‌های ماشین، $\alpha$ و $\beta$ از مجموعه‌ی ۰ تا ۹ و $x$ یکی از اعداد +۱ یا ۱- است. ($S_i$ و $S_j$ می‌توانند یکسان باشند، همین‌طور $\alpha$ و $\beta$). مفهوم این دستور این است که اگر ماشین در حالت $S_i$ باشد و در خانه‌ای که هد روی آن قرار گرفته است، رقم $\alpha$ نوشته شده باشد، ماشین به حالت $S_j$ می‌رود و در خانه‌ای از حافظه که هد روی آن قرار گرفته است و پیش از این $\alpha$ در آن نوشته شده بود، $\beta$ را می‌نویسد و اگر هد قبلا در خانه‌ی $k$ بوده باشد، به خانه‌ی $k+x$ تغییر مکان می‌دهد. اگر ماشین در حالت $S_r$ باشد و درخانه‌ای از حافظه که هد روی آن قرار گرفته است، رقم $\alpha$ ذخیره شده باشد، ولی در برنامه دستوری به صورت $(S_r,\alpha) \rightarrow …$ وجود نداشته باشد، ماشین متوقف می‌شود.

• سوال بعد
• سوال قبل