Yazan : Şadi Evren ŞEKER
Literatürde deutsch problem olarak geçen bu problem Ali ve Bekir arasında yaşanan bir tahmin problemidir. Basitçe Ali dilediği bir sayıyı seçip (0 veya 1 olarak ikilik tabandaki bir sayı seçecek) Bekir’e yollar. Bekir aldığı bu mesajı bir f(x) fonksiyonuna sokarak sonucu Ali’ye geri yollar.
Bekir f(x) fonksiyonunu kendisi seçebilmektedir ve seçtiği bu fonksiyon iki ihtimalden birisi olabilir:
- f(x) fonksiyonu bir sabit fonksiyondur, yani x değerinden bağımsız olarak sürekli 0 veya 1 üreten bir fonksiyon olabilir
- f(x) fonksiyonu eşit miktarda (%50 ihtimalle) 0 ve 1 üreten bir fonksiyondur
Ali yolladığı 1 ve 0 değerlerinin karşılığında aldığı sonuçlara göre, Bekir’in hangi tipte f(x) fonksiyonu kullandığını bulmaya çalışır.
Deutsch problemi, bu bulma işleminin kaç denemede yapılabileceğini sorar.
Bu adımları aşağıdaki şekiller üzerinden açıklamaya çalışalım:
Yukarıdaki şekilde görüldüğü üzere, 1. Adımda, Ali, Bekir’e bir değer yollar (1 veya 0) bu değeri kendi f fonksiyonuna koyan Bekir, sonucu Aliye geri yollar (sonuç yine 1 veya 0 olacaktır).
Yukarıdaki bu işlem istenildiği kadar tekrarlanabilir. Amaç, Ali’nin Bekir’in f fonksiyonunu en kısa sürede tahmin edebilmesidir.