هدف پروژه: طراحی یک ماشین تورینگ برای محاسبه تابع x5
این ماشین می تواند به این صورت که عرض می کنم پیاده سازی شود:
نحوه پیاده سازی:
به این صورت که ما از چپ 5 را به صورت unary می نویسیم. سپس یک Blank قرار می دهیم. سپس x که عدد ورودی است را به صورت unary می نویسیم و سپس Blank قرار می دهیم تا بین 5 و x فاصله بیافتد. سپس عدد 1 را می نویسیم و سپس Blank. در حال حاضر سه عدد به تفکیک وجود دارند که با Blank از هم جدا شده اند.
عدد اول از سمت راست در ابتدا 1 است و در هر مرحله در عدد وسطی که همان X است ضرب می شود و حاصل اش در سمت راستش چاپ می شود، سپس عدد سمت راست بجایش J قرار داده می شود تا در دفعات بعدی از آن عبور کنیم.
باید به تعداد سمت چپ(5 بار)، عدد وسطی را در راستی ضرب کنیم. در نهایت x5 را به صورت unary در سمت راست خواهیم داشت.
BX11111B11C1B
BX1111BB11CJ11B
BX111BBB11CJJ1111B
BX11BBBB11CJJJJ11111111B
BX1BBBBB11CJJJJJJJJJJJJ1111111111111111B
BXBBBBBB11CJJJJJJJJJJJJJJJJJJJJJJJJJJJJ11111111111111111111111111111111B
برای پیاده سازی توان از ماشین ضرب کننده x * y استفاده می کنیم.
برسی کد:
- پیاده سازی ماشین ها:
یک کلاس TuringMachine تعریف کردم که تعدادی متود و فیلد دارد:
o
toRight(): اشاره گر به سمت راست می رود
o
toLeft():
اشاره گر به سمت چپ می رود
o
run():
ماشین شروع به کار می کند و نتیجه خروجی را چاپ می کند (نوار را)
o
next(): ماشین
حالت بندی یک مرحله به جلو می رود (خواندن، تصمیم گیری، نوشتن و حرکت)
o
:write() یک
کاراکتر روی نوار می نویسد
o
:setState() تغییر حالت میدهد
o
:read() کاراکتر
روی نوار را می خواند (اشاره گر به آن اشاره می کند)
o
Index:
اشاره گر روی نوار (int)
o
Tape: یک
لیست از کاراکتر های روی نوار (list)
o
State:
وضعیت فعلی ماشین (string)
o
Finish: کار
ماشین تمام شده است (Bool)
دو ماشین دیگر بر همین اساس تعریف کردم یکی ماشین MultiplingMachine که عمل ضرب انجام می دهد و دیگری X5Machine که ماشین تابع x5 است. هر دوی این کلاس ها از TuringMachine ارث می برند. و تابع next آنها override می شود. که متغییر های فعلی را می گیرد و یک مرحله به جلو می رود. در واقع هر ماشین تورینگ، توابع انتقالش در همین متود next تعریف می شود.
ماشین ضرب کننده در یکی از حالات ماشین تابع x^5 استفاده می شود به این صورت که هنگام آماده بودن operand ها، این ماشین روی نوار صدا زده می شود تا حاصل را محاسبه کند.
پیاده سازی ماشین ضرب کننده (MultiplingMachine):
این ماشین دو عدد را می گیرد به صورت Unary و حاصل را بعد از آنها روی نوار چاپ می کند:
Input: (B<operand1>C<operand2>B)
B11C1111BB
Output: <B<operand1>C<J><result>B>
B11CJJJJJ11111111BB
