ماشین تورینگ متقارن
ماشین تورینگ متقارن ماشین تورینگی است که یک گراف پیکر بندی بدون جهت دارد (پیکر بندی i پیکر بندی j را نتیجه می‌دهد اگر و تنها اگر پیکر بندی j پیکر بندی i را نتیجه دهد)
تعریف ماشین تورینگ متقارن
در تعریف این ماشین‌ها به صورت رسمی، دسته‌ای از ماشین‌های تورینگ را با استفاده از مجموعه از انتقال‌ها به شکل (p,ab,D،cd,q) تعریف می‌کنیم که در آن p و q نشان دهنده وضعیت‌های ماشین، ab و cd زوج‌هایی از نمادها و D نشان دهنده جهت حرکت کلاهک است.
ماشین در وضعیت p قرار دارد و روی نوار یک a و سپس b نوشته شده‌است. کلاهک روی نماد b قرار دارد. اگر جهت حرکت (D) چپ باشد، کلاهک ماشین، a و b را به c و d تغییر می‌دهد و به سمت چپ حرکت می‌کند و ماشین از وضعیت p به q منتقل می‌شود. معکوس این انتقال (q,cd,-D,ab,q)هم امکان‌پذیر است. اگر جهت حرکت (D) به سمت راست باشد، کلاهک و ماشین مانند حالت قبل عمل می‌کنند.
کلاهک این خاصیت را دارد که بتواند روی یک خانه از نوار قرار داشته باشد و با حرکتش هم‌زمان مقدار آن خانه و خانه دیگری را تغییر بدهد. وجود این خاصیت ضروری نیست اما تعریف را آسان تر می‌کند.
این ماشین‌ها اولین بار در سال ۱۹۸۲ توسط Lewis و Papadimitriou تعریف شدند.[1][2] آن‌ها به دنبال رده‌ای بودند که بتوانند مسئلهٔ UTSCON را، که وجود مسیر بین دو رٲس S و T از یک گراف بدون جهت را بررسی می‌کند، در آن جای دهند.
تا قبل از تعریف این ماشین‌ها، این مسائل، علی‌رغم آن که به عدم قطعیت نیازی نبود، فقط می‌توانستند در رده NL قرار بگیرند .(نوع متقارن STCON در رده NL کامل قرار داشت). ماشین تورینگ‌های متقارن نوعی از ماشین‌های تورینگ هستند که قدرت عدم قطعیت کمی دارند و ثابت شده‌است که قدرتشان حدالاقل برابر باDFA است، در واقع چیزی بین این ۲ حالت هستند.
((STIME(T(n رده زبان‌هایی است که توسط یک ماشین تورینگ متقارن با مرتبهٔ زمانی ((O(T(n) پذیرفته می‌شوند. با به حدالاقل رساندن عدم قطعیت در (NTIME(T (یعنی نوشتن رشته بدون قطعیت انجام شود ولی محاسبات به صورت قطعی انجام شوند)، می‌توان نشان داد که (STIME(T) = NTIME(T.
SL=L
((SSPACE(S(n رده زبان‌هایی است که با مرتبهٔ حافظه ((O(S(n. توسط ماشین تورینگی متقارن پذیرفته می‌شوند و ((SL=SSPACE(log(n.
SL می‌تواند معادل رده مسائل logspace کاهش پذیر به USTCON، تعریف شود .Lewis و Papadimitriou، طبق تعریفشان، با ساخت یک ماشین غیر قطعی برای USTCON که بتواند یک ماشین تورینگ متقارن معادل بسازد، این موضوع را نشان دادند. آن‌ها با بررسی خواص محاسباتی ماشین تورینگ متقارن و پیکر بندی خاص آن، مانند پیکر بندی گراف‌های بدون جهت، دریافتند که هر زبانی درSL، logspace کاهش پذیر به USTCONاست
در سال ۲۰۰۴ Omer Reingold، با نشان دادن یک الگوریتم قطعی برای USTCON که مرتبهٔ حافظهٔ آن لگاریتمی است، ثابت کرد که SL=L.[3] و برای این اثبات در سال ۲۰۰۵ جایزه Grace Murray Hopper Award و در سال ۲۰۰۹ به صورت مشترک با Salil Vadhan و Avi Wigderson جایزهٔGödel Prize را دریافت کرد.
اثبات از ضرب زیگزاگی گراف‌ها برای ساخت expander گراف‌ها به صورت بهینه، استفاده می‌کند
ملاحظات
- Jesper Jansson. Deterministic Space-Bounded Graph Connectivity Algorithms. Manuscript. 1998.
- Harry R. Lewis and Christos H. Papadimitriou. Symmetric space-bounded computation. Theoretical Computer Science. pp.161-187. 1982.
- Reingold, Omer (2004). "Undirected ST-Connectivity in Log-Space". Electronic Colloquium in Computational Complexity. 094.
منابع
- Lecture Notes :CS369E: Expanders in Computer Science By Cynthia Dwork & Prahladh Harsha
- Lecture Notes
- Sharon Bruckner Lecture Notes
- Deterministic Space Bounded Graph connectivity Algorithms Jesper Janson