Öğüt alan çift yönlü sonlu makineler

Bir hesaplama modeline karakter dizisi formatında dışarıdan yapılan güvenilir yardıma öğüt denir. Öğüt alan makineler, Damm ve Holzer'ın makalesinden itibaren çalışılmaktadır. Yakın zamanda Küçük ve ark. öğütün girdinin önüne eklendiği eski usulden farklı olarak öğütün ayrı bir teypte durduğu ve özel bir öğüt kafasıyla erişildiği yeni bir öğütlü makine modeli ortaya attılar. Biz de bu çalışmada Küçük ve ark.'nın tanımladığı bu modeli (ilk kez çoklu girdi kafaları özelliğini de ekleyerek) çalışacağız. Girdi boyunun öğüt boyunun bir polinomu ile sınırlı olduğu ve öğüt boyunun da girdi boyunun bir polinomu ile sınırlı olduğu, ayrıca tüm kafaların çift yönlü olduğu makineler için girdi kafaları ile öğüt kafaları arasında bir alışveriş imkanı olduğunu göstereceğiz. Frei ve ark. öğüt boyunun yeterince yavaş arttığı durumlarda tek yönlü bir girdi kafası ve çift yönlü bir öğüt kafasına sahip belirlenimci sonlu makinelere ne belirlen- imcilik kısıtını kaldırmanın, ne girdi kafasına çift yönlü hareket serbestliği tanımanın, ne de herhangi bir sayıda çift yönlü öğüt kafası eklemenin yardım edebileceğini iddia etti. Bu iddianın kanıtı olarak önerilen argümandaki hatayı gösterip iddianın aksini kanıtlayacağız. Öğüt miktarının sabit olmadığı her durumda tek yönlü bir girdi kafası ve tek yönlü bir öğüt kafasına sahip belirlenimci olmayan makinelerin bile tek yönlü bir girdi kafasına ve herhangi bir sayıda çift yönlü öğüt kafasına sahip belirlenimci makinelerce tanınamayan bir dili tanıdığını göstereceğiz. Frei ve ark. ayrıca L/poly problem sınıfının öğüt alan sonlu makineler cinsin- den bir karakterizasyonunu geliştirdiklerini iddia ettiler. Bu iddianın kanıtında tespit ettiğimiz bir problemi göstereceğiz.