ماشین محاسباتی «هاتی» دارای $n$ خانه‌ی حافظه‌ی $M_1$، $M_2$، …، و $M_n$ است. هر یک از این خانه‌های حافظه می‌توانند یکی از مقادیر ۰ یا ۱ را در خود ذخیره کنند. برای راحتی کار اعداد ذخیره‌شده در خانه‌های حافظه را با یک رشته به طول $n$ از ۰ و ۱ نمایش می‌دهیم که در آن $M_1$ عنصر سمت چپ است: $(M_1,M_2,…,M_n)$.

هاتی می‌تواند دو نوع دستورالعمل ساده را اجرا کند:

• دستورِ C i. در این دستور i یک عدد صحیح بین ۱ تا $n$ است. با اجرای این دستور، عدد ذخیره شده در خانه‌ی حافظه‌ی $M_i$ عوض می‌شود (از ۰ به ۱ و از ۱ به ۰ تغییر می‌کند).
• دستورِ D i. در این‌جا نیز i یک عدد صحیح بین ۱ تا $n$ است. هاتی برای اجرای این دستور عدد ذخیره شده در تمامی خانه‌های حافظه به‌ جز $M_i$ را بررسی می‌کند: درصورتی‌ که تمامی این مقادیر ۱ بودند، فقط عدد ذخیره‌شده در $M_i$ را عوض می‌کند، و در غیر این صورت (اگر حداقل یکی از آن‌ها صفر بود) تغییری در مقادیر خانه‌ها ایجاد نمی‌کند.

مثلاً فرض کنید هاتی ۳ خانه‌ی حافظه دارد که مقادیر $(0,0,1)$ در آن ذخیره شده‌اند. حال اگر دستور C 2را به ماشین بدهیم،این مقادیر تبدیل به $(0,1,1)$ خواهند شد. در ادامه اگر دستور D 1را وارد کنیم، حاصل برابر $(۱,۱,۱)$ می‌شود. اما اگر دستور D 1را قبل از دادن دستور C 2به ماشین می‌دادیم، حاصل همان $(0,0,1)$ باقی می‌ماند . یک «جدول صورت مسأله»، جدولی شامل $2^n$ سطر و ۲ ستون است که در هر ستون آن تمامی رشته‌های به طول $n$ از ۰ و ۱، هر رشته دقیقاً یک‌بار، آمده است. به رشته‌های ستون اول «رشته‌های ورودی» و به رشته‌های ستون دوم «رشته‌های خروجی» می‌گوییم. ما باید برای هاتی یک «برنامه» بنویسیم به نحوی که اگر هر یک از رشته‌های ورودی در خانه‌های حافظه‌ی هاتی باشد، پس از اجرای این برنامه، رشته‌ی خروجی هم‌سطر با آن رشته‌ی ورودی در حافظه‌ی هاتی قرار گرفته باشد.

یک برنامه شامل چند دستورالعمل است که پشت سر هم نوشته شده‌اند. هنگامی‌ که یک برنامه را به هاتی بدهیم، دستورالعمل‌های این برنامه به ترتیب اجرا می‌شوند. مثلاً فرض کنید هاتی ۲ خانه‌ی حافظه دارد ($n=2$) و جدول صورت مسأله‌ی زیر داده شده است:

یک برنامه‌ی نمونه که این کار را انجام می‌دهد به‌ صورت زیر است:

الف) یک جدول صورت مسأله را «ساده» می‌نامیم اگر در آن هر رشته‌ی ورودی مساوی رشته‌ی خروجیِ هم‌سطرش باشد، به‌ جز دو رشته‌ی $A$ و $B$ که این دو رشته فقط در یکی از $n$ عنصر خود با هم تفاوت داشته باشند. توجه کنید که در این جدول، $A$ رشته‌ی خروجی هم‌سطر با رشته‌ی ورودی $B$ و هم‌چنین $B$، رشته‌ی خروجی هم‌سطر با رشته‌ی ورودی $A$ است. ثابت کنید که می‌توان برای هر جدول صورت مسأله ی ساده، یک برنامه نوشت.

ب) ثابت کنید که می‌توان برای هر جدول صورت مسأله، یک برنامه نوشت.

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