حمید رضا عسگری | 1398.05.16

ماشین تورینگ (Turing Machine) چیست؟ بیت­‌کوین و اتریوم کدامیک تورینگ کامل هستند؟

امروزه یکی از مباحثی که در میان کامیونیتی شبکه های بلاک‌چینی و توسعه کاربردهای آنها در بین افراد مطرح می­گردد به این اصطلاح برخورد می­کنیم که آیا این شبکه ها تورینگ کامل هستند یا خیر؟ در این مقاله نگاهی گذرا به این امر خواهیم داشت. با کوین‌ایران همراه باشید.

ماشین تورینگ

مفهوم ماشین تورینگ به عنوان یک ماشین محاسباتی، اولین بار توسط “آلن تورینگ” ریاضی دان و دانشمند انگلیسی درسال 1936 میلادی ارائه گردید. ریشه این نظریه اقتباس از نظریه ماشین محاسباتی چارلز بابیج (1834) است.  این ماشین یک دستگاه فرضی است شامل یک نوار با طول نامتناهی از هر طرف و یک هد خواندن/نوشتن که می­تواند با یک مکانیزم بسیار ساده اطلاعات را از روی این نوار برطبق یک سری قوانین بخواند یا بنویسد. در هر حالت این نوار فقط به اندازه یک خانه به سمت راست یا چپ حرکت کرده و هد دستگاه روی آن یک خانه قرار می­گیرد و پس از خواندن نشانه­ی آن خانه با توجه به برنامه موجود تصمیم می­‌گیرد آن نشانه بدون تغییر باقی بماند و یا اینکه نشانه دیگری در آن خانه نوشته شود.

فرضیه آلن تورینگ برای ابداع این ماشین این است که بتوان هر نوع محاسبات پیچیده را توسط این مکانیزم ساده انجام داد (هرچند که از نظر تئوری ممکن است زمان بینهاتی لازم باشد). حافظه این ماشین ساختار بسیار ساده ای دارد. در واقع یک آرایه یک بعدی است که از دو طرف نامحدود است و می­تواند اطلاعات را به هر شکلی فراخوانی نماید.

turing machine

مکانیزم کار دستگاه طوری است که هِد دستگاه در هر وضعیت روی یک خانه قرار گرفته و فقط می­‌تواند اطلاعات همان خانه از نوار را بخواند یا بنویسد. کنترل این فرایند بر اساس یک برنامه (program) از نوع ماشین وضعیت (state machine) است که دنباله ای از وردودی ها را به خروجی مورد نظر تبدیل کرده و در محل مشخص روی نوار می­‌نویسد یا از روی آن می­‌خواند.

state machine

برای مثال نحوه کار ماشین وضعیت در شکل فوق بدینگونه است:

حالت اولیه یا شروع از q0: اطلاعات خانه ای که مقابل هد دستگاه است خوانده شده اگر 1 باشد در همان خانه 0 می­نویسد و هد به سمت چپ حرکت می­کند و ماشین به وضعیت q1 می­‌رود.

در وضعیت q1: تکرار (loop) است. مادامی که دیتای خوانده شده 1 باشد، مقدار آن 0 شده و هد به سمت چپ می­رود. با خواندن اولین 0 مقدار 1 شده و ماشین به وضعیت q2 می­‌رود.

در وضعیت q2: با خواندن مقدار 0 تغییری انجام نشده و هد به سمت چپ می­رود و با خواندن مقدار 1 تغییری انجام نشده و هد به سمت راست می­رود. در هر دو حالت وارد وضعیت q0 می‌­شود.

در اینجا با خواندن 0 تغییری در مقدار انجام نمی­شود اما وارد وضعیت Halt یا توقف می­شود. وضعیت qh برای اجتناب از تکرار نامتناهی، لازم و ضروری است.

یک ماشین تورینگ می­تواند محاسبات و عملگر های زیر را داشته باشد:

  • عملگرهای ریاضی (+, -, *) با هر ترتیب
  • حلقه (loop)
  • انتقال یا انشعاب (Go to)
  • شرط (If then else)

چنانچه یک ماشین همه خاصیت های فوق را باهم داشته باشد به آن “ماشین تورینگ کامل” (Turing Completeness) گفته می­‌شود.

اتریوم یا بیت‌­کوین، کدامیک تورینگ کامل است؟

برای پاسخ به این سوال بهتر است نگاهی بیاندازیم به کدهای محاسباتی اتریوم و بیت­‌کوین و ببینیم هریک چه خصوصیاتی دارند.

بیت‌کوین:

در شبکه بیت­‌کوین هر نود شبکه برای پردازش تراکنش ها از اسکریپت های تعیین شده در این شبکه یا همان آپ کد ها (OpCodes) استفاده می­‌کند. این آپ کد ها دارای دستورات محاسباتی معین و محدود بوده و نحوه اجرای آنها بر اساس مکانیزم اِستَک (stack-based) است. در این مکانیزم که در شکل زیر نشان داده شده، اطلاعات وارد یک آرایه ای یک بعدی از حافظه شده و فراخوانی و اجرا همیشه از بالاترین (آخرین) ورودی انجام می‌­شود. به عبارت دیگر استک دارای مکانیزم “آخرین ورودی-اولین خروجی” (Last-in, First-out) است. هیچ نوع پرش و حلقه ای (loop) در دستورات بیت­‌کوین وجود ندارد.

Stack

با توجه به خاصیت هایی که برای یک ماشین تورینگ کامل در بالا گفته شد، بیت­‌کوین تورینگ کامل نیست زیرا حلقه، انشعاب و پرش در دستورات وجود ندارد. سوال اینجاست که آیا این نقطه ضعفی برای بیت­‌کوین است؟ قطعا اینگونه نیست و اصولا پروتکل بیت‌­کوین و ماهیت وجودی آن نیازی ندارد به اینکه بخواهد ماشین تورینگ کامل باشد.

بیتشتر بخوانید: واژه نامه بیت‌کوین

bitcoin stack

اتریوم:

در شبکه اتریوم زبان برنامه نویسی (به عنوان مثال solidity) که برای تعریف اسمارت کانترکت ها و اجرای دستورات و پردازش تراکنش ها استفاده می‌­شود یک زبان برنامه نویسی کامل است و طبیعتا قابلیت اجرای دستورات و محاسبات پیچیده را دارد. در شکل زیر نیز یک نمونه از کد برنامه نویسی این زبان نشان داده شده است. همانگونه که دیده می­‌شود کلیه خاصیت های یک ماشین تورینگ کامل (از جمله حلقه، انشعاب، شرط) را دارد. بنابراین شبکه اتریوم یک ماشین تورینگ کامل محسوب می‌­گردد.

ethereum solidity

نکته ای که در اینجا مطرح می‌­شود این است که آیا وجود این خاصیت ها در کد برنامه نویسی در شبکه اتریوم خطری برای پایداری این شبکه محسوب نمی‌­شود؟ به عنوان مثال اگر یک برنامه نویس مخرب با این هدف در کد برنامه اش یک حلقه بی پایان (endless loop) قرار دهد و این کد روی تمام نودهای شبکه منتشر گردد، کل شبکه اسپم شده و مختل خواهد شد. شبکه اتریوم برای مقابله با این شرایط چه راهکاری برای پایدار ماندن شبکه دارد؟

پاسخ به این سوال در وجود مکانیزم سوخت (Gas) در این شبکه نهفته است. در تعریف پروتکل شبکه اتریوم برای اجرای هر واحد محاسباتی (مثل عملگرهای جمع، ضرب، انشعاب، حلقه و …) یک مقدار مشخصی از این سوخت که مقدار کارمزدی (fee) از جنس کوین شبکه (اِتِر) است باید خرج گردد. از آنجا که این کارمزد را باید ارسال کننده تراکنش یا اسمارت کانترکت پرداخت نماید لذا نمی­‌تواند حلقه بی نهایت اجرا کند چرا که در هر بار اجرای حلقه مقداری سوخت مصرف می­‌شود و به محض اتمام کارمزدِ پرداخت شده برای آن تراکنش یا قرارداد، در هر مرحله ای اجرای آن برنامه قطع می‌­شود. بنابراین چنین کاری برای آن فرد مخرب مقرون به صرفه نیست و به این ترتیب از اسپم شدن شبکه جلوگیری می­‌شود.

بیشتر بخوانید: زبان برنامه نویسی اتریوم

 

Sources: 1, 2, 3, 4, 5, 6, 7, 8, 9