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

برای مثال، فرض کنید که برنامه‌ی ماشین به صورت زیر باشد:

$$(S_0,1) \rightarrow (S_0,2,+1) \\ (S_0,2) \rightarrow (S_0,2) \rightarrow (S_0,1,+1)$$

در این صورت اگر در ابتدا در خانه‌های 0 تا $k$ حافظه دنباله‌ای از رقم‌های ۱ و ۲ و در بقیه‌ی خانه‌های حافظه رقم 0 ذخیره شده باشد، پس از انجام عملیات ماشین و متوقف شدن آن، دنباله‌ی نوشته شده در خانه‌های 0 تا $k$ به این صورت عوض می‌شود که همه‌ی ۱ ها تبدیل به ۲ و همه‌ی ۲ ها تبدیل به ۱ می‌شوند.

الف) فرض کنید در ابتدا در خانه‌های 0 تا $k$ حافظه دنباله‌ای از رقم‌های 0 و ۱ و در بقیه‌ی خانه‌های حافظه رقم ۹ ذخیره شده باشد. هم‌چنین فرض کنید که رقم نوشته شده در خانه‌ی 0 برابر 0 باشد. رقم‌های نوشته شده در خانه‌های 0 تا $k$ بسط دودویی یک عدد مثل $n$‌ را مشخص می‌کنند. برای مثال اگر وضعیت نوار به صورت زیر باشد

عدد $n=59(111011)_2$ مشخص می‌کند. برنامه‌ای بنویسید که پس از اجرای آن و متوقف شدن ماشین، در خانه‌های 0 تا $k$ یک دنباله‌ از رقم‌های 0 و ۱ و در بقیه خانه‌ها رقم ۹ نوشته شده باشد و دنباله نوشته شده در خانه‌های 0 تا $k$ عدد $n+1$ را مشخص کند. برای مثال اگر وضعیت اولیه نوار به صورت فوق باشد، پس از انجام عملیات ماشین باید به صورت زیر شود.

ب) فرض کنید در ابتدا در خانه‌های 0 تا $k$‌حافظه دنباله‌ای از رقم‌های 0 و ۱ و در بقیه‌ی خانه‌های حافظه ۹ ذخیره شده باشد. برنامه‌ای برای این ماشین بنویسید که پس از انجام عملیات ماشین و متوقف شدن آن، در خانه‌های 0 تا $k$ و نیز در خانه‌های $k+1$ تا $2k+1$ همان رشته‌ی اولیه نوشته شده باشد. به عبارت دیگر برنامه‌ی شما باید دنباله‌ی نوشته شده در خانه‌های 0 تا $k$ رادر خانه‌های $k+1$ تا $2k+1$ کپی کند. برای مثال، اگر وضعیت اولیه نوار به صورت زیر باشد:

پس از انجام عملیات ماشین، وضعیت نوار باید به صورت زیر باشد:

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