ماشین تورینگ متقارن

ماشین تورینگ متقارن ماشین تورینگی است که یک گراف پیکر بندی بدون جهت دارد (پیکر بندی i پیکر بندی j را نتیجه می دهد اگر و تنها اگر پیکر بندی j پیکر بندی i را نتیجه دهد)
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
در تعریف این ماشین ها به صورت رسمی، دسته ای از ماشین های تورینگ را با استفاده از مجموعه از انتقال ها به شکل (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 تعریف شدند. آن ها به دنبال رده ای بودند که بتوانند مسئلهٔ UTSCON را، که وجود مسیر بین دو رٲس S و T از یک گراف بدون جهت را بررسی می کند، در آن جای دهند.
تا قبل از تعریف این ماشین ها، این مسائل، علی رغم آن که به عدم قطعیت نیازی نبود، فقط می توانستند در رده NL قرار بگیرند .(نوع متقارن STCON در رده NL کامل قرار داشت). ماشین تورینگ های متقارن نوعی از ماشین های تورینگ هستند که قدرت عدم قطعیت کمی دارند و ثابت شده است که قدرتشان حدالاقل برابر باDFA است، در واقع چیزی بین این ۲ حالت هستند.