یک کامپیوتر دارای حافظه‌ای است که می‌تواند یک لیست از عددها (که هر کدام از آن‌ها ۰، ۱ یا ۲ هستند) را نگه‌داری کند. محدودیتی در طول لیستی که در حافظه‌ی این کامپیوتر نگه‌داری می‌شود وجود ندارد. این کامپیوتر می‌تواند یک برنامه را اجرا کند. هر برنامه شمال تعدادی دستور است که به ترتیب مشخصی قرار گرفته‌اند. این کامپیوتر تنها سه نوع دستور‌العمل را قبول می‌کند که عبارت‌اند از:

• $E\quad x$ ( $x$ یکی از عددهای ۰، ۱ یا ۲ است.): این دستور، عدد $x$ را به انتهای (سمت راست) لیست عددها اضافه می‌کند و پس از آن دستور بعدی را انجام می‌دهد.

• $D$ : عددی که در ابتدای (سمت چپ) لیست عددها قرار دارد را از لیست برمی‌دارد. اگر این عدد ۰ بود، دستور بعدی را اجرا می‌کند؛ اگر ۱ بود، یک دستور را جا می‌اندازد و دستور بعد از آن را اجرا می‌کند؛ و اگر ۲ بود، دو دستور را جا می‌اندازد و دستور بعدی را اجرا می‌کند.

• $J\quad d$ ( $d$ ک عدد صحیح مثبت یا منفی است.): اگر $d$ مثبت بود، دستوری که $d$ تا بعد از دستور فعلی است و اگر $d$ منفی بود، دستوری که $d$ تا قبل از دستور فعلی است را اجرا می‌کند.

اجرای برنامه با اجرای دستورالعمل اول آن شروع می‌شود و مطابق با قوانین فوق ادمه می‌یابد. اگر در یک مرحله، دستورالعملی که قرار است اجرا شود، وجود نداشت (برای مثال به یک دستور $J$ به یک دستور که در برنامه وجود ندارد پرش کردیم)، اجرای برنامه متوقف می‌شود. همچنین اگر لیست عددهای خالی بود و به دستورالعمل $D$ برخوردیم، برنامه متوقف می‌شود.

برای مثال برنامه‌ی زیر را در نظر بگیرید. (شماره‌های نوشته شده در سمت چپ دستورات، نشان‌دهنده‌ی ترتیب اجرای آن‌هاست.) در صورتی که پیش از اجرای این برنامه لیست عددها 1,1 باشد، با اجرای این برنامه به ترتیب دستورات شماره‌ی ۱، ۳، ۵، ۶، ۳ و ۴ اجرا می‌شوند و پس از آن، برنامه متوقف می‌شود. پس از متوقف شدن برنامه، لیست عددها خالی خواهد بود.

$1.D$

$2.E\quad 1$

$3.D$

$4.J\quad 4$

$5.E\quad 0$

$6.J\quad -3$

فرض کنید که یک لیست که یک لیست از عددهای ۰ و ۱ در حافظه‌ی این کامپیوتر قرار دارد. (توجه کنید که لیست، شامل عدد ۲ نیست.) برنامه‌ای برای این کامپیوتر بنویسید که پس از اجرای آن، این لیست برعکس شود. در مورد برنامه‌ای که می‌نویسید توضیح دهید.