Günlük uzay dönüştürücü - Log-space transducer

Bir günlük alanı dönüştürücü (LST) bir tür Turing makinesi için kullanılır günlük alanı azaltmaları.

Bir kütük alanı dönüştürücü, ${displaystyle M}$, üç kasete sahiptir:

• Salt okunur giriş bant.
• Bir okuma / yazma iş bant (en fazla ${displaystyle O (log n)}$ semboller).
• Yalnızca yazılır, bir kez yazılır çıktı bant.

${displaystyle M}$ hesaplamak için tasarlanacak günlük alanı hesaplanabilir işlevi ${displaystyle fcolon Sigma ^ {ast} ightarrow Sigma ^ {ast}}$ (nerede ${displaystyle Sigma}$ ... alfabe ikisinin de giriş ve çıktı bantlar). Eğer ${displaystyle M}$ ile yürütülür ${displaystyle w}$ onun üzerinde giriş bant, makine durduğunda ${displaystyle f (w)}$ onun üzerinde kalan çıktı bant.

Dil ${displaystyle Asubseteq Sigma ^ {ast}}$ olduğu söyleniyor log-space azaltılabilir bir dile ${displaystyle Bsubseteq Sigma ^ {ast}}$ eğer varsa günlük alanı hesaplanabilir işlevi, ${displaystyle f}$, bir girdiyi problemden dönüştürecek ${displaystyle A}$ problemin girdisine ${displaystyle B}$. I.E. ${displaystyle B'de Aiff f (w) kazandı}$.

Bu oldukça kıvrımlı bir fikir gibi görünse de, indirgeme için arzu edilen iki yararlı özelliğe sahiptir:

1. Geçişlilik özelliği geçerlidir. (A, B'ye azalır ve B, C'ye düşer, A'nın C'ye indirgemesi anlamına gelir).
2. A, B'ye düşerse ve B, L o zaman A'nın içinde olduğunu biliyoruz L.

Geçişlilik devam eder çünkü bir redüktörün (A → B) çıkış bandını diğerine (B → C) beslemek mümkündür. İlk bakışta bu yanlış görünüyor çünkü A → C redüktörünün çıkış bandını B → C redüktörüne beslemek için A → B redüktöründen iş bandına depolaması gerekiyor, ancak bu doğru değil. B → C redüktörünün giriş bandına her erişmesi gerektiğinde, A → C redüktörü A → B redüktörünü yeniden çalıştırabilir ve bu nedenle A → B redüktörünün çıktısının tamamen aynı anda depolanması gerekmez.

Referanslar

• Szepietowski, Andrzej (1994), Sublogaritmik Uzaylı Turing Makineleri , Springer Basın, ISBN  3-540-58355-6. Erişim tarihi: 2008-12-03.
• Sipser, Michael (2012), Hesaplama Teorisine Giriş, Cengage Learning, ISBN  978-0-619-21764-8.