[GM. 4] Hex, tam bilgili oyunlar ve strateji çalma

[GM] serisinin bu yazısında 1942’de Piet Hein bulunan ve 1947’de bağımsız olarak John Nash tarafından tekrar keşfedilen Hex oyununu inceleyeceğiz.

Hex, hücreleri altıgen olan eşkenar dörtgen biçimindeki bir tahtada oynanan bir masaüstü oyunu. Oyun tahtası geleneksel olarak 11 x 11 boyutunda olsa da 13 x 13 ve 19 x 19 boyutundaki çeşitlemeler de mevcut.

Hex iki oyuncu ile oynanıyor ve her oyuncu bir renge sahip. Bu blog yazısı için oyuncuların renkleri mavi ve kırmızı olsun. Hex tahtasının her bir kenarı karşılıklı kenarlar aynı renk olmak üzere mavi ve kırmızı renkleriyle işaretleniyor.

Oyunun kuralları basit. Her oyuncu sırası geldiğinde tahtaya kendi renginde bir taş yerleştirerek o renge sahip kenarlar arasında (bağlantılı) bir yol oluşturmaya çalışıyor. Mesela aşağıda mavi oyuncunun kazandığı bir Hex oyunu görüyoruz.

hex.png

Oyunu özümsemek için bilgisayara karşı Hex oynamak isterseniz şu adreste bir uygulama mevcut. Bu yazıda şunları kanıtlayacağız

  • Hiçbir Hex oyunu berabere bitemez.
  • Hex’te birinci oyuncunun bir kazanma stratejisi vardır.

Birinci oyuncunun bir kazanma stratejisi olduğunu okuyunca oyunun bir anlamı kalmadığını düşünebilirsiniz. Öte yandan bilmenizde fayda var ki birinci oyuncunun kazanma stratejisinin ne olduğu bilinmiyor, sadece böyle bir strateji olduğu biliniyor. Sanıyorum ki bu durum yapıcı olmayan kanıtlara aşina olmayan pek çok okuyucu için şaşırtıcı bir durum. Nasıl oluyor da birinci oyuncunun bir kazanma stratejisi olduğunu böyle bir stratejiyi açık açık bulmadan gösterebiliyoruz? Yazının ilerleyen bölümlerinde bunun John Nash tarafından yapılmış basit ve zarif bir kanıtını göreceğiz ancak şimdiden anahtar kelimeyi vermek istiyorum: Strateji çalmak.

Birinci oyuncunun -henüz ne olduğunu bilmesek de- bir kazanma stratejisi olduğunu öğrendiğimize göre bu noktada Hex’e bazen dahil edilen bir değişim kuralından bahsetmekte fayda var. Bu kurala göre birinci oyuncu ilk hamlesini yaptıktan sonra ikinci oyuncuya renkleri değiştirme fırsatı verilir. Böylece, ikinci oyuncu birinci oyuncunun ilk hamlesinde çok stratejik bir pozisyonu ele geçirdiğini düşünürse renkleri değiştirerek bu avantajı kendisi ele geçirebilir.

Hex teoremi

Yazının bu bölümünde Hex’in berabere bitemeyeceğini kanıtlayacağız. Bu teoremi daha sonra birinci oyuncunun bir kazanma stratejisi olduğunu kanıtlamakta kullanacağız. Okuduğum kadarıyla John Nash bu teoremin kanıtını 1952’de yapmış ancak bu kanıta ne yazık ki erişemedim. Bu yazıda Nash’in kanıtı yerine David Gale’ın ilgili 1979 makalesindeki kanıtı yapacağız.

Teorem: Hex tahtası sırasıyla mavi ve kırmızı taşlarla doldurulursa oyunu mavi oyuncu veya kırmızı oyuncu kazanır. Yani Hex oyunu berabere bitemez.
Kanıt (Taslak): Hex tahtasına aşağıda görüldüğü gibi dört nokta ve dört kenar ekledikten sonra oluşturduğumuz düzlemsel çizgedeki ilgili dört bölgeyi ilgili kenarların renklerine aşağıdaki gibi boyayalım.

hex2.png

Diyelim ki mavi ve kırmızı oyuncular oyunu oynayıp tahtayı kırmızı ve mavi taşlarla doldurdular. Her hücrenin rengini o hücreye konan ilgili taşın rengi olarak atayalım. Şimdi yapacağımız şey yukarıdaki çizgenin bir alt çizgesini oluşturmak. Oluşturacağımız alt çizgenin noktalar kümesi aynı olsun, kenarları da şu kurala uygun biçimde seçelim.

  • Asıl çizgedeki bir kenar alt çizgeye dahildir ancak ve ancak bu kenarın ayırdığı iki bölgenin renkleri farklı ise.

Örneklemek açısından, aşağıdaki şekilde doldurulmuş bir tahta üzerinde oluşturduğumuz alt çizge turuncu ile işaretlenmiş kenarları içeren çizge olacak.

hex3.png

Şimdi kanıtlarını okuyucuya egzersiz olarak bırakacağım iki önsav göreceğiz.

Önsav 1: Oluşturduğumuz alt çizgedeki noktaların dereceleri 0, 1 ya da 2 olabilir.
Önsav 2: Noktalarının dereceleri en fazla 2 olan sonlu bir çizge

  • izole noktaların (yani derecesi 0 olan noktaların),
  • basit döngülerin (yani kendini kesmeyen döngülerin) ve
  • basit yolların (yani kendini kesmeyen yolların)

ayrık birleşimi olarak  yazılabilir.

Biraz uğraşla kolayca gösterilebilir ki oluşturduğumuz alt çizgede derecesi 1 olan noktaların ilk başta eklediğimiz dört noktadan ibarettir. Dolayısıyla, Önsav 2’nin bir sonucu olarak, oluşturduğumuz alt çizgede bu noktaları birbirine bağlayan basit yollar olmak zorunda.

(Eğer Jordan eğri teoremi gibi şeylerden haberdarsanız, bu basit yolların eklediğimiz noktalardan karşılıklı olanları birbirine bağlayamacağını da kanıtlayabilirsiniz.)

Ne elde ettik? Hex tahtası mavi ve kırmızı taşlarla doldurulduğu zaman yukarıdaki prosedürle elde ettiğimiz alt çizge, ilk başta eklediğimiz dört noktayı ikili olarak birbirine bağlayan iki basit yol içeriyor. Bu basit yolların kenarlarının üzerinde olduğu altıgen hücreler takip edilerek de karşılıklı kenarları birbirine bağlayan bir altıgen hücre zinciri olmak zorunda olduğu kanıtlanabilir. (Mesela sağ aşağıdaki noktayı sağ üstteki noktaya bağlayan bir yol varsa oyunu kırmızı kazanmıştır, aksi halde sağ aşağıdaki noktayı sol alttaki noktaya bağlayan bir yol varsa oyunu mavi kazanmıştır vs.) \blacksquare

Yukarıda taslağını verdiğimiz kanıt Gale’in orijinal makalesinden ya da şuradaki ders notlarından da okunabilir. Kanıtın fikri basit ve şık. Tabii matematiksel kesinlikten ödün vermemek adına kanıtı olabildiğince biçimselleştirmek istersek, özellikle kanıtın sonlarına doğru, bir miktar hammallık yapmak zorunda kalacağız. Bu yüzden her yeri sembol yığınına boğmak yerine kanıtın taslağını vermeyi tercih ettim -aynı Gale’ın yaptığı gibi!

Yukarıdaki teoremdeki veya ifadesini ya ya da ifadesine çevirebiliriz. İki oyuncunun aynı anda kazanamayacağı, yani karşılıklı kenarları bağlayan hem kırmızı hem de mavi taşlar zinciri olamayacağı, sezgisel olarak açık olmalı. Öte yandan bunu matematiksel olarak kanıtlamak için Jordan eğri teoremini kullanmak zorundayız. (Aslında Gale’ın makalesinin ikinci bölümünde yazana göre bunun Lichtenstein tarafından yapılan tamamen kombinatoriyel bir kanıtı da mevcutmuş.)

Bu noktada belirtmeliyim ki fazladan iş yükü çıkarttığından dolayı ilgili teoremin ya ya da çeşitlemesini kanıtlamayacağız ve kanıtsız kabul ederek yazıya devam edeceğiz.

Hex’in belirliliği

Hex’in berabere bitemeyeceğini kanıtladığımıza göre şimdi birinci oyuncunun bir kazanma stratejisi olduğunu gösterebiliriz.

Önsav: Hex’te ya birinci oyuncunun ya da ikinci oyuncunun bir kazanma stratejisi vardır.
Kanıt: Göstermek istediğimiz önerme şu önermeye denk: Eğer ikinci oyuncunun bir kazanma stratejisi yoksa, o zaman birinci oyuncunun bir kazanma stratejisi vardır.

Bunu kanıtlayabilmek için küçük bir tanıma ihtiyacımız var. Oyundaki bir pozisyona birinci oyuncu için kaybeden pozisyon diyelim ancak ve ancak bu pozisyondan itibaren ikinci oyuncunun bir kazanma stratejisi varsa, yani tahta bu pozisyona geldiğinde ikinci oyuncu kazanmayı garantileyen bir strateji bulabiliyorsa.

Şimdi önemli bir gözlem yapalım. Bir pozisyon birinci oyuncu için kaybetmeyen bir pozisyonsa, birinci oyuncu öyle bir hamle yapabilir ki ikinci oyuncu ne hamle yaparsa yapsın ortaya çıkan pozisyon birinci oyuncu için gene kaybetmeyen bir pozisyon olacaktır. Aksi halde ilk başta içerisinde bulunduğumuz pozisyon birinci oyuncu için kaybetmeyen bir pozisyon olmazdı! Demek ki birinci oyuncu kaybetmeyen bir pozisyondaysa, kendini tekrar kaybetmeyen bir pozisyona sokacak bir hamle yapabiliyor.

Şimdi kanıtın ilk satırında yazdığımız önermeyi kanıtlamaya hazırız. Diyelim ki ikinci oyuncunun bir kazanma stratejisi yok. Bu durumda birinci oyuncunun bir kazanma stratejisi olduğunu göstermek istiyoruz.

İkinci oyuncunun bir kazanma stratejisi olmadığına göre boş tahta birinci oyuncu için kaybetmeyen bir pozisyondur. Yukarıda yaptığımız gözlem gereği de birinci oyuncu öyle bir hamle yapabilir ki (ikinci oyuncu ne yaparsa yapsın) kendini tekrar kaybetmeyen bir pozisyona sokabilir. Benzer şekilde birinci oyuncu her hamlesinde kendini kaybetmeyen bir pozisyona sokacak bir hamle yapsın, ki böyle bir hamle yapabileceğini biliyoruz.

Birinci oyuncu için (tümevarımla) inşa ettiğimiz bu strateji bir kazanma stratejisi olmak zorundadır. Aksi halde, eğer birinci oyuncu oyun sonunda kaybetseydi, ikinci oyuncunun kazanmayı garantilediği bir pozisyon bulabilirdik ve bu da tümevarım hipotezimizle çelişirdi.

Demek ki Hex’te ikinci oyuncunun bir kazanma stratejisi yoksa birinci oyuncunun bir kazanma stratejisi olmak zorunda. Dolayısıyla Hex’te ikinci oyuncunun veya birinci oyuncunun bir kazanma stratejisi vardır. İki oyuncunun aynı anda kazanma stratejisi olamayacağına göre bir önceki cümledeki veya bağlacını ya da olarak değiştirebiliriz. \blacksquare

(Yukarıda yaptığımız şey aslında tam bilgili sonlu iki kişilik oyunlar için geçerli olan Zermelo’nun teoremini Hex için kanıtlamak. Yaptığımız kanıt da sonsuz oyunlardaki Gale-Stewart teoreminin kanıtının ta kendisi.)

Şimdi yazının ana teoremini kanıtlayabiliriz.

Teorem: Hex’te birinci oyuncunun bir kazanma stratejisi vardır.
Kanıt (Nash): Önceki yazdıklarımızın bir sonucu olarak birinci oyuncunun ya da ikinci oyuncunun bir kazanma stratejisi olması gerektiğini biliyoruz.

Diyelim ki ikinci oyuncunun bir kazanma stratejisi var. Bu durumda birinci oyuncu bu kazanma stratejisini kolayca çalabilir:

İlk hamle olarak rastgele bir hamle yapsın. Daha sonra ikinci oyuncu sanki birinci oyuncu, kendisi de ikinci oyuncuymuş gibi davranarak ikinci oyuncunun kazanma stratejisini uygulasın. Eğer bu strateji herhangi bir noktada ilk başta rastgele yaptığı hamlenin yapılmasını gerektiriyorsa (o hamle zaten ilk başta yapıldığı için) başka bir hamle yaparak devam etsin.

Dikkat edilmesi gereken nokta Hex’te yapılan fazladan bir hamlenin bir oyuncuyu içerisinde bulunduğu durumdan daha kötü bir pozisyona sokamayacağı. Yani bir oyuncu bir hücre boşken oyunu kazanmayı garantileyebiliyorsa o hücreye fazladan bir taş koyarak da oyunu kazanmayı garantileyebilir. Dolayısıyla yukarıda birinci oyuncunun ikinci oyuncunun stratejisini çalarak geliştirdiği strateji kendisi için bir kazanma stratejisidir.

Demek ki ikinci oyuncunun bir kazanma stratejisi varsa birinci oyuncu bunu çalıp kendisi için bir kazanma stratejisi üretebiliyor. İki oyuncunun aynı anda kazanma stratejileri olamayacağına göre ikinci oyuncunun bir kazanma stratejisi olamaz. Demek ki birinci oyuncunun bir kazanma stratejisi olmak zorunda. \blacksquare

Birinci oyuncu oyunu nasıl kazanır?

Hex’te birinci oyuncunun bir kazanma stratejisinin var olması gerektiğini biliyoruz. Öte yandan, 2016 itibariyle 11 x 11’lik standart tahtalar için bir kazanma stratejisi açık açık bulunmuş değil. Bununla birlikte tahta boyutunu küçültüp 9 x 9’luk Hex ile ilgilenirsek, bilgisayarlar yardımıyla birinci oyuncunun stratejisi bulunmuş durumda.

Yazıyı noktalamadan önce birkaç küçük not ekleyim. Hex’te verilen bir pozisyonun kazanan bir pozisyon olup olmadığını anlamak PSPACE-tam bir problemmiş. Son olarak, matematikçilerin ilgisini çekebilecek bir bilgi. Hex’in belirliliği (yani ya birinci oyuncunun ya da ikinci oyuncunun bir kazanma stratejisi olması) kullanılarak Brouwer sabit nokta teoremi, daha doğrusu bu teoremin birim kare üzerindeki özel hali, kanıtlanabiliyor. Bunun tersi de doğru, Brouwer’in sabit nokta teoremiyle Hex’in belirliliğini kanıtlamak da mümkün. Bu kanıtları görmek isteyenler Gale’ın bağlantısını verdiğim 1979 makalesini inceleyebilir.

C.N.

Reklamlar

[GM. 3] Iraksak serileri toplamak ve -1/12

GM serisinin bu yazısında ıraksak serileri toplamak için ne gibi yöntemler olduğunu göreceğiz. Yazının ana temalarından birisi Numberphile denen YouTube kanalının ilgi çekmek için geniş halk kitlelerinin kafasını karıştırmak suretiyle kullandığı

1+2+3+\dots=\frac{-1}{12}

eşitliği olacak. Bu eşitliğin hangi bağlamda doğru olduğunu anlamaya çalışacağız. Benzer şekilde

1-1+1-1+\dots=\frac{1}{2}

ve

1-2+3-4+\dots=\frac{1}{4}

eşitliklerinin de hangi bağlamda doğru olduğunu öğreneceğiz.

Yazının başından çeşitli uyarılarda bulunmak istiyorum. Hayır, bu teoremlerin kanıtları ilgili toplamlara s dedikten sonra eşitlikleri cebirsel olarak manipüle edip ilgili s değeri bulunarak yapılmıyor. Numberphile ve çeşitli diğer YouTube videolarında görebileceğiniz bu argümanların kanıtladığı şey aslında şu: Eğer bu serilere (daha sonra göreceğimiz) belirli özellikleri sağlayan uygun bir toplam atama yöntemi varsa, o zaman bu serilerin toplamları ilgili sayılar olmalı. Öte yandan böyle toplam atama yöntemlerinin neden var olması gerektiği açık değil.

Toplam atama yöntemi derken neyi kastediyorum? Sonsuz toplamları bırakıp önce sonlu toplamlarla ilgilenelim.

2+2 niye 4 eder?

Matematik Öklit’ten beri belitsel olarak işleyen bir disiplindir. Bunun anlamı şu, matematikte çeşitli belitleri doğru kabul ederiz ve mantıksal çıkarımlar yaparak teoremler kanıtlarız.

Bundan dolayıdır ki matematik diğer bilimlerden farklı olarak kesindir. Bir kanıtın doğru olup olmadığı mekanik olarak kontrol edilebilir. Dolayısıyla, eğer bir kanıt doğruysa, farklı bir mantık sisteminde çalışmadığınız ya da belitlerinizi değiştirmediğiniz sürece doğru olarak kalacaktır. Bunları niye anlattım?

2+2=4 eşitliği neden doğrudur? Çarpım tablosunda yazdığı için mi? Yoksa her || ile || çokluğunu yan yana getirdiğimizde |||| çokluğunu elde ettiğimizi gördüğümüz için mi? İkisi de değil. Eğer 2+2’nin 4 ettiğini kanıtlamak istiyorsak önce bir belitsel sistem seçmeli, daha sonra 2, 4 ve + sembollerinin ne anlama geldiğini bu belitsel sistem içerisinde tanımlamalı, daha sonra da bu eşitliği belitlerimizi kullanarak türetmeliyiz. Bunu yapmanın pek çok yolu var. Mesela belitsel sistemimizi sadece doğal sayılarla ilgilenen Peano belitleri seçersek 2+2’nin 4 ettiğini kanıtlamak çok zor değil. Bunun yerine, neredeyse bilinen tüm matematiği içerisinde yapabileceğiniz ZFC belitleri altında çalışırsak, doğal sayıları ve toplama işlemini çeşitli kümeler olarak inşa ettikten sonra 2+2’nin 4 olduğunu kanıtlayabiliriz. Matematik Dünyası‘nın eski sayılarından 2×2 özel sayısını okursanız 2×2’nin neden 4 olduğunu öğrenebilirsiniz!

Tüm bunları niye yazdım? Matematiğin tümdengelimsel bir şekilde işlediğini gözünüze sokmak için. Dolayısıyla matematiksel bir iddiada bulunmak istediğinizde, iddianızdaki terimlerin ne olduğunu tanımlamalısınız ki belitlerimiz vasıtasıyla doğru ya da yanlış olduğunu kanıtlamaya çalışalım.

Sonlu toplamların ne olduklarını ve nasıl yapıldıklarını biliyoruz. Peki ya sonsuz toplamlar?

Yazıya devam etmeden önce gerçel sayıları inşa ettiğimizi ve diziler, seriler ve limit gibi temel calculus kavramlarını bildiğimizi varsayacağım. Burada gerçel sayılarla çalışmak için özel bir nedenimiz yok. Aslında çok daha geniş bir çerçevede çalışabiliriz ama yazı GM serisinde olduğu için geniş halk kitlelerinin kafasını karıştırmamak adına herkesin aşina olduğu bir sayı sisteminde çalışmak daha iyi olacaktır.

Yakınsak ve ıraksak seriler

Elimizde elemanları gerçel sayılar olan bir (a_n)_{n \in \mathbb{N}^+} dizisi olsun. Sonlu toplamların ne olduğunu bildiğimizi varsaymıştık. Her n \in \mathbb{N}^+ için S_n = a_1+a_2+\dots+a_n  olarak tanımlayalım. Üniversitede calculus dersi almış her zeki, çevik ve ahlaklı gencin bilmesi gerektiği gibi eğer öyle bir L gerçel sayısı varsa ki

\displaystyle \lim_{n \rightarrow \infty} S_n=L

oluyorsa bu durumda

\Sigma_{n=1}^{\infty}\ a_n=a_1+a_2+\dots

serisine yakınsak bir seri diyoruz. Eğer bir \Sigma_{n=1}^{\infty} a_n serisi yakınsak değilse, bu durumda ona ıraksak seri diyoruz. Bir seri yakınsaktır ancak ve ancak kısmi toplamlar dizisinin bir limiti varsa. Iraksak serilere örnek olarak

\Sigma_{n=1}^{\infty} \frac{1}{n}=\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\dots

\Sigma_{n=1}^{\infty} n=1+2+3+\dots

\Sigma_{n=1}^{\infty} (-1)^{n+1}=1-1+1-1+\dots

\Sigma_{n=1}^{\infty} (-1)^{n+1} \cdot n=1-2+3-4+\dots

serilerini gösterebiliriz. Bu serilerin hiçbirinin kısmi toplam dizisinin limiti yoktur.

Biraz düşünürseniz siz de kolayca kanaat getirebilirsiniz ki bu tanım sahip olduğumuz sonsuz toplam sezgisiyle büyük ölçüde örtüşen bir tanım: Eğer sonsuz tane sayıyı toplamaya çalışıyorsak, sayıları teker teker eklemeye devam ettiğimizde elde ettiğimiz kısmi toplamın nasıl bir davranış sergilediğine bakmalıyız, değil mi?

Çeşitli serilerin kısmi toplamlarının limiti olmadığını görüyoruz. Dolayısıyla bu toplam tanımı altında toplanamayan seriler var. Peki bu noktada pes mi etmeliyiz?

Iraksak serileri toplamak

Hikaye odur ki gelmiş geçmiş en önemli matematikçilerden biri olan David Hilbert bir öğrencisinin şair olmak için dersini bıraktığını öğrendiğinde “İyi, zaten matematikçi olabilmek için yeterli hayal gücü yoktu.” demiştir.

Bu anekdotu anlatma sebebim şu. Üç beş kısmi toplam dizisinin limiti yok diye matematikçiler ıraksak serileri toplamaya çalışmaktan vazgeçecek değil ya?!

Yukarıda bir toplama tanımı yaptık. Bir \Sigma_{n=1}^{\infty}\ a_n serisinin toplamının ne olduğuna kısmi toplamlar dizisinin limitine bakarak karar verdik. Daha sonra fark ettik ki elimizde bu tanım altında toplanamayan bir yığın seri var.

Peki öyle bir toplam tanımı yapabilir miyiz ki hem yakınsak serileri toplamaya çalıştığımızda yukarıda yaptığımız standart toplam tanımıyla örtüşsün hem de bazı ıraksak serileri de toplamamıza olanak versin? Bu sorunun yanıtı olumlu.

Cesaro toplamı

Verilen bir (a_n)_{n \in \mathbb{N}} dizisi için \Sigma_{n=1}^{\infty}\ a_n serisinin Cesaro toplamını şu şekilde tanımlayalım.

\Sigma_{n=1}^{\infty}\ a_n=L \Leftrightarrow L=\displaystyle \lim_{n \rightarrow \infty} \frac{S_1+S_2+\dots+S_n}{n}

Yani bir serinin Cesaro toplamı L‘dir ancak ve ancak serinin kısmi toplamlarının ortalamalarının limiti L ise. Biraz uğraşla gösterilebilir ki eğer bir \Sigma_{n=1}^{\infty}\ a_n serisi standart toplam tanımı altında yakınsaksa ve toplamın değeri L ise bu durumda bu serinin Cesaro toplamı da L‘dir. Öte yandan bunun tersi doğru olmak zorunda değil. Mesela

\Sigma_{n=1}^{\infty} (-1)^{n+1}=1-1+1-1+\dots

serisinin kısmi toplamları dizisine baktığımızda elde edeceğimiz dizi

(S_n)_{n \in \mathbb{N}^+}=(1,0,1,0,\dots)

olacaktır. Bu kısmi toplamlar dizisinin ilk n teriminin ortalamasını alarak elde ettiğimiz diziyse

(\frac{S_1+S_2+\dots+S_n}{n})_{n \in \mathbb{N}^+}=(\frac{1}{1},\frac{1}{2},\frac{2}{3},\frac{2}{4},\frac{3}{5},\frac{3}{6},\dots)

olacaktır. Bu dizinin limiti \frac{1}{2} olduğundan 1-1+1-1+\dots serisinin Cesaro toplamı \frac{1}{2} olur.

Demek ki Cesaro toplamı standart toplama tanımını genelliyor ve ıraksak bazı serilere de toplam atamamıza izin veriyor. Peki Cesaro toplamı altında toplanamayan seriler var mıdır? Evet vardır. Örneğin

\Sigma_{n=1}^{\infty} (-1)^{n+1} \cdot n=1-2+3-4+\dots

serisinin Cesaro toplamı yoktur zira kısmi toplamların ortalamasını alarak elde ettiğimiz dizinin limiti yoktur. Demek ki Cesaro toplamıyla da toplayamadığımız seriler var.

Hikaye burada bitecek mi? Tabii ki hayır. Aynen Cesaro toplamının standart toplam tanımını genellemesi gibi Cesaro toplamını genelleyecek bir tanım yapmayı deneyebiliriz. Cesaro toplamını tanımlarken ne yapmıştık? Kısmi toplamların limitine bakmak yerine kısmi toplamların ortalamalarının limitine bakmıştık. Peki bir adım daha öteye gidip kısmi toplamların ortalamalarının ortalamalarının limitine bakarsak ne olacak?

Biraz uğraşla bu yaptığımız yeni toplam tanımının Cesaro toplamını genellediği gösterilebilir. Üstüne üstlük, bu tanım altında

\Sigma_{n=1}^{\infty} (-1)^{n+1} \cdot n=1-2+3-\dots=\frac{1}{4}

olacaktır. Peki bu yeni toplam tanımıyla bu sefer tüm serilere sonlu bir toplam atamayı başarmış olabiliriz miyiz? Ne yazık ki hayır.

Bu tanım altında da toplanamayan seriler var. Mesela

\Sigma_{n=1}^{\infty} n=1+2+3+\dots

serisi bu tanım altında da toplanamaz. Peki bu bizim için bir engel mi? Değil.

Durmak yok, yola devam! Yeni bir tanım yapalım. Aynen Cesaro toplamını genellediğimiz gibi, bu yeni tanımı da genelleyelim. Kısmi toplamların ortalamalarının ortalamalarının limitine bakmak yerine kısmi toplamlarının ortalamalarının ortalamalarının ortalamalarının limitine bakalım. Bu da yetmezse kısmi toplamların ortalamalarının ortalamalarının… Cesaro toplamını bu şekilde ya da başka şekillerde genellemek mümkün.

Peki bu toplam tanımlarını kafamıza göre mi yapıyoruz?

Sonsuz serilere toplam atamaya çalışmak

Sonsuz serilere toplam atayabilmek için yaptığımız bu tanımları kafamıza göre yapmıyoruz. Yaptığımız tanımların belirli özellikleri sağlamasını istiyoruz.

Birinci olarak, yaptığımız tanım düzgün olmalı. Yani standart toplam tanımı altında yakınsak olan serilere aynı değerleri atamalı.

İkinci olarak, yaptığımız tanım doğrusal olmalı. Yani eğer \Sigma_{n=1}^{\infty}\ a_n=L_1 ve \Sigma_{n=1}^{\infty}\ b_n=L_2 oluyorsa, her c sabiti için \Sigma_{n=1}^{\infty}\ c \cdot a_n+b_n=c \cdot L_1+L_2 olmalı.

Üçüncü olarak, yaptığımız tanım stabil olmalı. Yani eğer \Sigma_{n=1}^{\infty}\ a_n=L oluyorsa, bir M pozitif tam sayısı için ilk M terimi atarak elde ettiğimiz \Sigma_{n=1}^{\infty}\ a_{n+M} serisini topladığımızda L-a_1-a_2-\dots-a_{M} bulmalıyız.

İlk özelliğin sağlanmasını istiyoruz çünkü yapacağımız toplama tanımı sezgisel olarak bize anlamlı gelen standart tanımla örtüşmeli. Diğer iki özelliğin sağlanmasını istiyoruz çünkü bu özellikler sağlanmadan bir serinin toplamını bulmak için herhangi bir cebirsel manipülasyon yapmak mümkün değil. Hani YouTube videolarında adam seriyi kaydırıyor, sabitlerle çarpıyor, paranteze alıyor ve terim terim topluyor ya. Hah işte, o işlemlerin hepsini ilgili seriye toplam atayan metodun bu özellikleri sağladığı varsayımı altında yapıyor.

Mesela Cesaro toplamı bu özelliklerin üçünü de sağlıyor. Peki bu özellikleri sağlayan başka toplam metodları var mı?

Abel toplamı

Yazının bu bölümünde 27 yaşındayken tüberkülozdan ölen Norveçli matematikçi Niels Hendrik Abel‘in ardından isimlendirilen Abel toplamını göreceğiz.

Verilen bir \Sigma_{n=0}^{\infty}\ a_n serisi için

f(x)=\Sigma_{n=0}^{\infty}\ a_n x^n

kuvvet serisini tanımlayalım. Eğer bu kuvvet serisinin 0 etrafındaki yakınsaklık yarıçapı 1 ise ve

\displaystyle \lim_{x \rightarrow 1^-} f(x)=L

limiti varsa, bu durumda verilen serinin Abel toplamıL olarak tanımlayalım. Mesela Abel toplamı altında

1-2+3-4+\dots=\frac{1}{4}

olacaktır zira

1-2x+3x^2-4x^3+\dots

kuvvet serisinin |x|<1 değerleri için tanımladığı fonksiyon olan

\frac{1}{(1+x)^2}

fonksiyonunun 1 noktasındaki soldan limiti \frac{1}{4}. Bu noktada fark etmeniz gereken önemli bir ayrıntı bu seri için Cesaro toplamının Hölder genellemesiyle elde ettiğimiz sonucun aynısını Abel toplamıyla da elde etmiş olmamız. Aslında bu bir tesadüf değil. Eğer düzgünlük, doğrusallık ve stabillik özelliğini sağlayan bir toplam yöntemi bu seriye değer atabiliyorsa, bu durumda atadığı değer 1/4 olmak zorunda. Bunun nedeni de YouTube videolarında itiraz edilen argümanın ta kendisi.

Bu noktada tekrar vurgulama gereği duyuyorum. Bu cebirsel manipülasyon ilgili serinin değerinin 1/4 olduğunu kanıtlamıyor. Kanıtladığı şey şu: Eğer düzgünlük, doğrusallık ve stabillik özelliğini sağlayan bir toplam yöntemi bu seriye bir toplam atayabiliyorsa, bu durumda serinin toplamı 1/4 olmak zorunda. Kısaca o videolarda hasır altı edilen şey yapılan cebirsel manipülasyona izin veren ve ilgili seriye toplam atayabilen bir yöntemin var olduğunun kanıtlanması.

Yazının bu bölümünü noktalarken Abel toplamının Cesaro toplamını genelleyen bir toplam yöntemi olduğunu ve listelediğimiz üç özelliğe de sahip olduğunu belirtme gereği duyuyorum.

Başka başka…

Cesaro toplamını gördük. Bunun (aslında aynı olan) iki farklı genellemesini gördük. Abel toplamını gördük. Sonsuz serilere toplam atamak için başka yöntemler var mı?

Daha pek çok yöntem var ancak bu blog yazısında yukarıdakilerden daha fazlasını görmeyeceğiz. Bunun iki nedeni var. Birincisi, ıraksak seriler matematiğin hakkında koca koca kitaplar ve onlarca makale yazılmış bir alanı. Dolayısıyla konunun küçük bir blog yazısında “özet” geçilmesi mümkün değil. İkincisi, konunun uzmanı bir insan değilim. Şu ana kadar anlattığım yöntemler ıraksak serilere toplam atamak için bilinen en popüler yöntemler. Size daha fazlasını aktarabilmek için benim de ilgili kitapları açıp okumam gerekiyor. Dürüst olmak gerekirse, öğrenmek istediğim ve öğrenmem gereken onca başka konu varken vaktimi buna harcamak istemiyorum. Dolayısıyla yok size başka toplam yöntemi.

Konuyla ilgili daha çok şey öğrenmek istiyorsanız yukarıda yazdığım yöntemleri ve çok daha fazlasını anlatan G. H. Hardy‘nin “Divergent Series” kitabını okuyabilirsiniz. Anladığım kadarıyla konu üzerine yazılmış önemli referans kitaplardan bir tanesi bu kitap. Bu kitabı okumasanız bile ilgili Wikipedia sayfasına ve bu sayfadaki referanslara göz atarak konu hakkında araştırma yapmanız gereken kaynakları görebilirsiniz.

Yazının sonuna yaklaşırken ünlü

1+2+3+\dots=\frac{-1}{12}

eşitliğine geçebiliriz. Öncelikle şunu bilmenizde fayda var. Düzgünlük, doğrusallık ve stabillik özelliklerini sağlayan hiçbir toplam yöntemi bu seriye bir toplam atayamaz. Bunun kısa bir kanıtı şu Wikipedia sayfasında bulunabilir. Demek ki bu seriye toplam atayabilecek her yöntem bu özellikleri sağlayamayacak kadar “garip” olmalı.

Bu seriye toplam atamak için Ramanujan toplamını kullanabiliriz. Bu cümleyi okuyunca az sonra Ramanujan toplamı hakkında konuşmaya başlayacağımı sanmış olabilirsiniz. Hayır, ne yazık ki konuyla ilgili bilgim an itibariyle sınırlı olduğu için kaş yaparken göz çıkartıp yanlış bilgilendirme yapmamak için sadece kaynak göstereceğim. Hardy’nin yukarıda bağlantısını verdiğim kitabının 323. sayfasından Bölüm 13.5’ten itibaren okumaya başlarsanız, bu toplam tanımının nereden geldiğini görebilirsiniz.

İlgili eşitliğe anlam vermenin başka bir yolu da Riemann zeta fonksiyonunu kullanmak. Riemann zeta fonksiyonu gerçel kısmı 1’den büyük karmaşık sayılar için

\zeta(s)=\Sigma_{n=1}^{\infty} \frac{1}{n^s}

şeklinde tanımlı bir fonksiyon. Buradaki sonsuz toplam bildiğimiz standart sonsuz toplam. Gerçel kısmı 1’den küçük eşit olan s değerleri içinse bu toplam yakınsak değil. Öte yandan çeşitli teknikler kullanarak bu fonksiyonu kompleks düzlemin s=1 hariç her noktasına fonksiyonun güzel özelliklerini koruyacak şekilde genişletmek mümkün. Bunu yaptıktan sonra da fonksiyon -1 noktasında tanımlı hale geliyor ve bu noktadaki değeri \frac{-1}{12} oluyor. Bunu da

\zeta(-1)=1+2+3+\dots=\frac{-1}{12}

olarak yorumlamak mümkün. Benzer teknikler kullanılarak başka serilere nasıl toplam atandığını görmek için şu sayfayı okuyabilirsiniz.

Sözün özü

Sözün özü, ıraksak serilerle ilgili sağda solda gördüğünüz sezgi karşıtı duran eşitliklerin hepsi aslında kendi bağlamlarında doğru eşitlikler. Burada anahtar kelime bağlam.

Yazının başında matematiğin tümdengelimsel olmasını boşuna okuyucunun gözüne sokmaya çalışmadım. Birisi size ıraksak bir seri verip bu serinin toplamının ilk bakışta saçma gözüken bir değer olduğunu iddia ediyorsa, ilk yapmanız gereken şey “Burada seriye toplam atamak için hangi tanım kullanılıyor?” sorusunu sormak.

Özellikle Ekşi Sözlük’te çok görüyorum Grandi serisine ya da 1-2+3-4+… gibi serilere sonlu toplamlar atandığını görüp herhangi bir Google araması bile yapmadan “Bu saçmalık, böyle şey olmaz; ona toplama S diyemezsin tamam mı yae!!11!111” diye çıkışan tipleri. Bak canım arkadaşım, bak canım kardeşim. Üzerine en az yüz küsür yıldır çalışılan şeylere üniversitede öğrendiğin iki üç mühendislik Calculus dersiyle herhangi bir araştırma yapmadan “saçmalık” demek cahilliğin eli bayraklı önde gidenidir. Rica ediyorum yapmayın şöyle şeyler. Bu güruha lafımızı çaktığımıza göre diğer güruha geçebiliriz.

Ayrıca buradan ıraksak serileri barındıran eşitlikleri sağda solda bağlamından kopartarak kullanıp piyasa yaparak ortada çok mistik bir şey varmış gibi sunan yoldaşlara sesleniyorum. Bu güruha Numberphile de dahil. Yapmayın canım arkadaşım, yapmayın canım kardeşim. Sizin yüzünüzden insanlar matematiği saçmalık sanıyor. Farkındayım size çok ilginç gelen bir şeyle karşılaşmış durumdasınız ama bunu insanlara yaymadan önce bir araştırın. Daha sonra olayı olabildiğince kendi bağlamında sunup kaynaklar vererek insanları araştırmaya yönlendirin. Aksi halde neden 1-2+3-4+\dots=\frac{1}{4} olduğunu anlamadan ya da anlamaya teşebbüs etmeden bu eşitliği yazmanın ne manası var?

C.N.


“Les s´eries divergentes sont en g´en´eral quelque chose de bien fatal et c’est une honte qu’on ose y fonder aucune d´emonstration. On peut d´emontrer tout ce qu’on veut en les employant, et ce sont elles qui ont fait tant de malheurs et qui ont enfant´e tant de paradoxes. . . . Enfin mes yeux se sont dessill´es d’une maniere frappante, cara l’exception des cas les plus simples, par exemple les s´eries g´eom´etriques, il ne se trouve dans les math´ematiques presque aucune s´erie infinie dont la somme soit d´etermin´ee d’une maniere rigoureuse, c’est-a-dire que la partie la plus essentielle des math´ematiques est sans fondement. Pour la plus grande partie les r´esultats sont justes il est vrai, mais c’est la une chose bien ´etrange. Je m’occupea en chercher la raison, probleme tres int´eressant.” -Niels Hendrik Abel, 16 Ocak 1826 tarihli bir mektubundan.

[GM. 2] Pergel ve cetvel ile imkansız çizimler

GM serisinin bu yazısında Antik Yunan’dan yadigar pergel ve cetvel inşalarını inceleyeceğiz ve çeşitli problemlerin çözümsüzlüğünü göstereceğiz. Yazının içeriğinin lise seviyesinde Öklit geometrisi görmüş herkes için anlaşılır olacağını umuyorum. İlgileneceğimiz problemler şunlar olacak. Pergel ve cetvel ile

  • Bir çember verildiğinde bu çemberle aynı alana sahip bir kare çizmek.
  • Birim uzunluk verildiğinde \sqrt[3]{2} uzunluğunu inşa etmek.
  • Bir açı verildiğinde bu açıyı üçe bölmek.
  • Düzgün çokgen çizmek.

Amacımız sadece pergel ve cetvel kullanarak ilk üç problemin çözülemeyeceğini göstermek ve üçüncü problemin çözülebilmesi için gerek ve yeter bir koşul bulmak.

Pergel ve cetvel inşası nedir?

Noktasal bir uca sahip bir pergel ve işaretsiz bir cetvelimiz olsun. Burada cetvelin işaretsiz olması önemli zira cetveli uzunluk ölçmek için değil sadece ve sadece elimizdeki noktaları birleştiren doğruları çizmek ve çizdiğimiz doğruları istediğimiz kadar uzatabilmek için kullanacağız.

Amacımız, elimizdeki ideal pergel ve işaretsiz cetveli kullanarak sonlu adım sonunda hangi uzunlukları, açıları ve düzgün çokgenleri inşa edebileceğimizi bulmak. Yapacağımız inşalar hakkında bir şeyler kanıtlamak istediğimiz için -doğal olarak- soruyu matematiksel bir zemine oturtmalıyız.

Bunun ilk adımı olarak da pergel ve cetvel kullanarak bir inşa gerçekleştirdiğimizde inşanın her adımında hangi işlemlerin yapılabileceğini tanımlamalıyız.

Bir pergel ve cetvel inşasının her adımında aşağıdaki temel işlemlerden birini yapabiliyoruz:

  • Elimizdeki iki noktadan geçen doğruyu çizmek.
  • Elimizdeki iki noktanın birini merkez alan ve diğerinden geçen çemberi çizmek.
  • Elimizdeki paralel olmayan iki doğrunun kesiştiği noktayı bulmak.
  • Elimizdeki bir doğrunun ve bir çemberin -eğer kesişiyorlarsa- kesişim noktalarını bulmak.
  • Elimizdeki iki çemberin -eğer kesişiyorlarsa- kesişim noktalarını bulmak.

Bu çizimlerin ideal bir pergel ve işaretsiz bir cetvel ile nasıl gerçekleştirilebileceği açık olmalı. Burada dikkat edilmesi gereken nokta bu işlemlerin hepsinin daha önceki adımlarda elde edilmiş noktalar, doğrular ve çemberler üzerinden tanımlanması. Yani bu temel işlemleri kullanarak bir pergel ve cetvel inşası gerçekleştirebilmek için bize ilk başta bir şeyler verilmiş olması gerekiyor!

Pergel ve cetvel ile gerçekleştirilebilen bazı operasyonlar

İlk bakışta yukarıdaki temel işlemleri uygulayarak fazla karmaşık şeyler yapamayacağımızı düşünebilirsiniz. Eğer böyle düşünüyorsanız, yanılıyorsunuz!

Yazının bu bölümünde pergel ve cetvel ile gerçekleştirilebilen bazı temel operasyonları göreceğiz. Bu operasyonların çoğunu yazının daha sonraki bölümlerinde -üstü kapalı olarak- kullanacağımız için her bir operasyonun nasıl yapıldığını anlamanız yazının kalanının anlaşılabilirliği açısından önemli.

Yazının bu bölümünü okurken anlatılacak çizimleri Euclid the Game isimli sitedeki uygulamayı kullanarak kendiniz de yapabilirsiniz.

  1. Bir doğru parçasının orta noktasını bulmak: Diyelim ki uç noktaları A ve B olan bir doğru parçası verildi. Pergelimizi |AB| kadar açtıktan sonra merkezi A ve B noktaları olan iki çember çizelim. Bu çemberler iki noktada kesişecektir; bu noktalar C ve D noktaları olsun. C ve D noktalarını birleştiren doğrunun verilen doğru parçasını kestiği nokta bu doğru parçasının orta noktası olacaktır. İlgili Euclid the Game bölümü.
    2
  2. Verilen bir açıyı ikiye bölmek: Diyelim ki iki ışın arasında kalan bir açı verildi. Bu ışınlardan biri üzerinde verilen ikinci bir noktamız olsun. Işınların kesiştiği noktaya A, ışınların biri üzerindeki ikinci noktaya da B diyelim. A merkezli |AB| yarıçaplı çemberi çizelim ve diğer ışını kestiği noktayı işaretleyelim, bu noktaya C noktası diyelim. B ve C noktalarını merkez alan ve |BC| yarıçaplı çemberleri çizelim. Bu çemberlerin kesiştiği iki noktadan birisini alalım. Bu nokta D noktası olsun. A ve D noktalarından geçen doğru BAC açısını ikiye bölecektir. İlgili Euclid the Game bölümü.
    3
  3. Verilen bir doğruya bu doğru üzerindeki bir noktadan dik çizmek: Bir doğru ve bu doğru üzerinde bir A noktası verildiğini varsayalım. Bu doğru üzerinde ikinci bir B noktası verilsin. A merkezli ve |AB| yarıçaplı çemberi çizerek bu çemberin doğruyla kesiştiği noktayı bulalım. Bu nokta C noktası olsun. B ve C noktalarını merkez alan |BC| yarıçaplı iki çember çizerek bu çemberlerin kesişim noktalarını bulalım. Bu noktaları birleştiren doğru A noktasından geçecek ve bize verilen ilk doğruya dik olacaktır. İlgili Euclid the Game bölümü.
    4.jpg
  4. Verilen bir doğruya bu doğru üzerinde olmayan bir noktadan dik çizmek: Diyelim ki elimizde bir doğru ve bu doğru üzerinde olmayan bir B noktası var. Bu doğru üzerinde olan bir A noktası verilsin. B merkezli ve |BA| yarıçaplı çemberi çizdikten sonra bu çemberin verilen doğruyla kesiştiği noktaya C diyelim. Birinci operasyonu kullanarak AC doğru parçasının orta noktasını bulalım. Bu nokta D noktası olsun. BD doğrusu verilen doğruya diktir. İlgili Euclid the Game bölümü.
    5
  5. Verilen bir doğruya üzerinde olmayan bir noktadan paralel çizmek: Diyelim ki elimizde bir doğru ve bu doğru üzerinde olmayan bir B noktası var. Dördüncü operasyonu kullanarak B noktasından geçen ve verilen doğruya dik olan bir doğru çizelim. Bu elde ettiğimiz yeni doğruya ve B noktasına üçüncü operasyonu uygularsak, verilen ilk doğruya paralel ve B noktasından geçen bir doğru elde edeceğiz. İlgili Euclid the Game bölümü.
    6.jpg
  6. Verilen bir noktadan verilen bir doğru parçasıyla aynı uzunlukta ve aynı doğrultuda bir doğru parçası çizmek: Diyelim ki uç noktaları A ve B olan bir doğru parçası ve bu doğru parçası üzerinde olmayan bir C noktası verildi. Beşinci operasyonu kullanarak A ve B noktalarından geçen doğruya paralel olan ve C noktasından geçen bir doğru çizebiliriz. Bu doğru L doğrusu olsun. Benzer şekilde, A ve C noktalarından geçen doğruyu çizdikten sonra bu doğruya paralel olan ve B noktasından geçen bir doğru da çizebiliriz. Bu doğru da K doğrusu olsun. K ve L doğrularının kesiştiği nokta D noktası olsun. CD doğru parçası AB ile aynı doğrultuda ve aynı uzunluktadır. İlgili Euclid the Game bölümü.
    7.jpg

Euclid the Game oyununu bitirmenizi tavsiye ediyorum zira ufuk açıcı bir oyun. Yazının devamında yapacaklarımız için yukarıda listelenen operasyonlar yeterli olduğundan dolayı pergel ve cetvelle gerçekleştirilebilecek diğer işe yarar operasyonları atlıyorum.

İnşa edilebilir sayılar

Hatırlayın, bir pergel ve cetvel inşasında izin verdiğimiz işlemlerin hepsi daha önceki adımlarda elde edilmiş noktalar, doğrular ve çemberler üzerinden tanımlanıyordu. Dolayısıyla herhangi çizim yapmaya başlayabilmek için bize ilk başta bir şeylerin verilmiş olması gerekiyor.

Çizimlerimizde ilk başta düzlem üzerinde işaretlenmiş iki tane nokta olduğunu varsayacağız. Bu noktalar arasındaki uzaklığı da birim uzunluk olarak alacağız.

Soru: Pergel ve cetvel kullanarak hangi uzunlukları inşa edebiliriz?

Yani aralarındaki uzaklık birim uzunluk olan iki nokta ile başlarsak izin verilen temel işlemleri uygulayarak sonlu adım sonunda hangi uzunlukları inşa etmek mümkün? Burada bir r uzunluğunu inşa etmekten kastımız, inşamızın sonunda aralarındaki uzaklık r olan iki nokta elde edebilmek.

Tanım: Bir r gerçel sayısına inşa edilebilir diyelim ancak ve ancak |r| uzunluğunu bir pergel ve cetvel inşası sonucunda elde edebiliyorsak.

Şimdi hangi sayıları inşa edebileceğimi hakkında düşünmeye başlayalım. Doğal sayıların -dolayısıyla tam sayıların- hepsi inşa edilebilirdir zira başlangıçta verilen iki noktadan geçen doğruyu çizdikten sonra her biri sonrakinin merkezinden geçen art arda çemberler çizerek tüm doğal sayıları elde edebiliriz. Mesela 4 sayısı inşa edilebilirdir zira

integer.jpg

Tam sayılar inşa edebilir olduğuna göre üçgen benzerliğini kullanarak rasyonel sayıların da inşa edilebilir olduğunu şu şekilde kolayca gösterebiliriz. Diyelim ki bir \frac{m}{n} rasyonel sayısının inşa edilebilir olduğunu göstermek istiyoruz. Kenarı birim uzunlukta olan bir eşkenar üçgen çizelim. Bu üçgenin iki kenarını içeren ışınları çizdikten sonra bu ışınlar üzerinde |m| ve |n| uzunluklarını elde edelim. Elde ettiğimiz bu uzunluklara sahip doğru parçalarının uç noktaları birleştiren doğruyu çizelim. Bu doğruya L doğrusu diyelim. Eşkenar üçgenin |m| ve |n| uzunluklarını veren doğru parçalarıyla kesişmediği iki köşesinden L doğrusuna paraleller çizersek, bu doğruların eşkenar üçgenin ilgili kenarlarını kestiği noktaların uzunlukları benzerlikten dolayı \frac{|m|}{|n|} ve \frac{|n|}{|m|} olacaktır. Mesela \frac{3}{5} rasyonel sayısı inşa edilebilirdir zira

rational

Öte yandan rasyonel olmayan uzunlukları da inşa edebileceğimizi biliyoruz. Zira birim eşkenar üçgen çizebildiğimize göre, bu üçgenin bir kenarına dik inerek \frac{\sqrt{3}}{2} uzunluğunu elde edebiliriz. Başka bir örnek verelim. Biraz uğraşla pergel ve cetvelle birim kare inşa edilebileceğini gözlemleyebilirsiniz. Ancak bu durumda, bu karenin köşegeninin uzunluğu olan \sqrt{2} sayısı inşa edilebilir bir sayıdır.

İnşa edilebilir sayıları karakterize etmek

Demek ki inşa edilebilir sayılar kümesi rasyonel sayıları içeren ancak rasyonel sayılardan daha büyük bir küme. Şimdi bu kümenin cebirsel yapısını anlamaya çalışalım.

Teorem: Eğer a ve b \neq 0 inşa edilebilir sayılarsa, o zaman a+b, a-b, ab ve \frac{a}{b} sayıları da inşa edilebilirdir.

Bu teoremin kanıtını okuyucuya egzersiz olarak bırakıyorum zira kanıt çok zor değil. Yazının bir önceki bölümündeki operasyonların nasıl yapılacağını boşuna göstermedik!

Bu yazı GM serisinde olduğu için fazla teknik terimler kullanmak istemiyorum ama bilenler için vurgulama gereği duyuyorum; yukarıdaki teorem bize inşa edilebilir sayıların gerçel sayıların bir alt cismi olduğunu söylüyor. Peki bu cismin başka ne özellikleri var?

Teorem: Eğer a > 0 inşa edilebilir bir sayıysa, o zaman \sqrt{a} sayısı da inşa edilebilirdir.
Kanıt: a inşa edilebilir pozitif bir sayı olsun. Bu durumda a+1 sayısı da inşa edilebilirdir. Şimdi uzunluğu a+1 olan bir doğru parçası (şekildeki HJ doğru parçası) çizdikten sonra bir numaralı operasyon yardımıyla bu doğru parçasının orta noktasını bulalım (şekildeki M noktası). Daha sonra merkezi bu nokta olan \frac{a+1}{2} yarıçaplı çemberi çizelim. a inşa edilebilir olduğuna göre çemberin çapını a ve 1 şeklinde bölecek noktayı bir pergel ve cetvel inşasıyla elde edebiliriz. Bu nokta I noktası olsun. Üçüncü operasyonu kullanarak I noktasından geçen ve çapa dik olan bir doğru çizelim. Bu doğrunun çemberle kesiştiği nokta N noktası olsun. Bu durumda NI doğru parçasının uzunluğu \sqrt{a} olacaktır. (Son basamaktaki iddianın neden doğru olduğunu anlamak için HNJ üçgeninin bir dik üçgen olduğunu fark edip bu üçgende Öklit bağıntısını uygulayın.) \blacksquare

squareroot.jpg

Demek ki inşa edilebilir gerçel sayıların oluşturduğu cisim pozitif elemanların kareköklerini alma işlemi altında kapalı. Daha teknik terimlerle konuşmak gerekirse, inşa edilebilir sayılar Öklityen bir cisim. Birazdan inşa edilebilir sayıların rasyonel sayıları içeren, aritmetik işlemler ve pozitif elemanların karekökünü alma işlemi altında kapalı olan gerçel sayıların en küçük alt kümesi olduğunu göreceğiz.

Hatırlayın, pergel ve cetvel inşalarını yapabilmemiz için düzlemde bize aralarındaki uzaklığı birim uzaklık aldığımız iki nokta verilmişti. Şimdi bu noktaların sırasıyla (0,0) ve (1,0) koordinatlarına sahip olduğu bir koordinat sistemi hayal edelim.

r inşa edilebilir bir sayı olsun. İnşa edilebilirliğin tanımı gereği öyle bir pergel ve cetvel inşası vardır ki bu inşa sonunda elde ettiğim noktalar içerisinde aralarındaki uzaklık |r| olan iki nokta bulabiliriz. Ancak aralarındaki uzaklık |r| olan iki nokta bulabiliyorsak, altı numaralı operasyonu uygulayıp bir ucu (0,0) olan |r| uzunluğunda bir doğru parçası da elde edebiliriz. Bu durumda (0,0) noktasını merkez alan |r| yarıçaplı çemberi çizip koordinat eksenleriyle kesiştirerek (|r|,0) noktasını elde edebiliriz.

Demek ki r inşa edilebilir bir sayıysa, öyle bir pergel ve cetvel inşası vardır ki bu inşanın sonunda koordinatları (|r|,0) olan nokta elde edilebiliyor. Böyle bir inşa alalım ve bu inşadaki adım sayısına n diyelim.

Her 0 \leq i \leq n için, K_i kümesi, inşanın i . adımı sonunda elde etmiş olduğumuz noktaların koordinatlarını içeren ve aritmetik işlemler altında kapalı gerçel sayıların en küçük alt kümesini belirtsin.

Burada aritmetik işlemler altında kapalı derken şunu kastediyoruz. Eğer a ve b kümenin elemanlarıysa, a+b,a-b,ab ve a/b sayıları da kümenin elemanlarıdır. Tabii sıfırla bölme yapmayı yasaklıyoruz. Dolayısıyla b=0 durumunda a/b sayısının kümede olmasını beklemiyoruz. Yazının geri kalanında da aritmetik işlemler altında kapalı terminolojisini kullandığımızda bunu kastediyor olacağız. Cisim kavramının ne olduğunu bilenler için teknik terimlerle konuşmak gerekirse, K_i kümesi i . adım sonunda elde ettiğimiz tüm noktaların koordinatlarını içeren en küçük cisim.

İnşanın sıfırıncı adımında, yani henüz hiçbir temel işlem uygulamamışken, elimizde koordinatları (0,0) ve (1,0) olan iki nokta olduğu için K_0=\mathbb{Q} olacaktır. Şimdi tüm dertlerimize derman olacak gözlem geliyor.

Önsav: Her 0 \leq i < n için

  • Ya K_{i+1}=K_i  olur, ya da
  • K_{i+1} kümesi, K_i kümesini ve \sqrt{m} \notin K_i olan pozitif bir m \in K_i sayısı için \sqrt{m} sayısını içeren aritmetik işlemler altında kapalı en küçük kümedir.

Kanıt: Pergel ve cetvel inşalarını gerçekleştirmemizi sağlayan temel işlemlere bakalım. Bu temel işlemler arasından yeni noktalar elde etmemizi sağlayanlar sadece son üç işlem. Bu son üç işlemde yeni noktalar elde ederken o ana kadar elde ettiğimiz noktaları kullanarak oluşturabildiğimiz doğruları ve çemberleri kesiştiriyoruz. Demek ki inşanın i+1. adımında elde edeceğimiz yeni nokta i. adımda elimizde olan doğruları ve çemberleri kesiştirmemiz sonucu elde edilebilir.

i. adım sonunda elimizde olan doğruların ve çemberlerin denklemlerini yazdığımızda bu denklemlerde göreceğimiz sabit terimler ve katsayılar K_i kümesinin elemanı olmak zorundadır. Dolayısıyla bu çemberleri ve doğruları kesiştirdiğimizde elde edeceğimiz noktaların koordinatları, doğrular birinci derece ve çemberler ikinci derece denklemlerle ifade edildiği için, katsayıları K_i kümesinde olan en fazla ikinci derece denklemlerin çözümlerinden gelecektir.

Eğer i+1. adımda elde ettiğimiz yeni nokta iki doğru kesiştirilerek elde ediliyorsa, bu durumda bu noktanın koordinatları K_i kümesinde olacaktır zira K_i kümesi aritmetik işlemler altında kapalı. Eğer i+1. adımda elde ettiğimiz yeni nokta bir çember ve bir doğrunun ya da iki çemberin kesişiminden elde ediliyorsa, ikinci derece denklemlerin çözüm formülü gereği bu noktanın koordinatları K_i kümesindeki bir pozitif elemanın karekökü ve aritmetik işlemler yardımıyla elde edilebilir. Eğer ilgili diskriminantın karekökü K_i kümesindeyse, bu durumda K_i =K_{i+1} olacaktır. Eğer ilgili diskriminantın karekökü K_i kümesinde değilse, bu durumda K_{i+1} tanımı gereği teoremin ikinci maddesini sağlamak zorunda kalacaktır. \blacksquare.

(Not: İki çemberi kesiştirdiğimiz zaman neden kesişim noktalarının koordinatlarını bulmak için ikinci derece bir denklem çözmenin yeterli olduğu bariz olmayabilir. Öte yandan elinize kalem kağıt alıp çözmeyi denerseniz böyle olması gerektiğini görebilirsiniz!)

Biliyoruz ki n adım sonunda (|r|,0) noktasını elde edebiliyoruz, yani  |r| \in K_{n}. Öte yandan, önsav gereği, her adımda elimizdeki noktaların koordinatlarını içeren en küçük cisim ya önceki adımda elde ettiğimiz cismin aynısı ya da önceki adımda elde ettiğimiz cisme bu cisimde karekökü olmayan pozitif bir elemanın karekökü eklenerek oluşturulmuş bir cisim. Demek ki her inşa edilebilir sayı bu şekilde elde edilebilmeli.

Biraz uğraşla bunun tersinin de doğru olduğunu gösterebilirsiniz. Yani öyle aritmetik işlemler altında kapalı \mathbb{Q}=K_0 \subseteq K_1 \subseteq \dots \subseteq K_n kümeleri bulabiliyorsanız ki her küme bir önceki kümeden bu kümedeki pozitif bir elemanın karekökü eklenip aritmetik işlemler altında kapatılarak elde ediliyorsa, bu durumda en son kümedeki her sayı inşa edilebilirdir.

Kısaca inşa edilebilir sayılar, rasyonel sayılarla başlayıp her adımda daha önceki adımlarda elinizde olan sayılara aritmetik işlemler uygulayarak ve karekök alarak sonlu adımda elde edebileceğiniz sayılardır.

Bu noktada geniş halk kitlesi falan dinlemeyip kanıtladığımız teoremin matematiksel olarak doğru halini yazma gereği duyuyorum.

Teorem: Bir r \in \mathbb{R} sayısı inşa edilebilirdir ancak ve ancak öyle bir \mathbb{Q}=K_0 \subseteq K_1 \subseteq \dots \subseteq K_n cisim kulesi varsa ki r \in K_n ve her 0 \leq i < n için [K_{i+1}:K_i] \leq 2 oluyorsa.

Çeşitli problemlerin çözümsüzlüğü

Yazının bu bölümünde saydığımız dört problemden ilk üçünün çözümü olmadığını göreceğiz. Bu problemlerin ne olduğunu hatırlayalım. Pergel ve cetvel ile

  • Bir çember verildiğinde bu çemberle aynı alana sahip bir kare çizmek.
  • Birim uzunluk verildiğinde \sqrt[3]{2} uzunluğunu inşa etmek.
  • Bir açı verildiğinde bu açıyı üçe bölmek.

Eğer birinci problemi çözebiliyor olsaydık, birim yarıçapa sahip çemberin alanı \sqrt{\pi} olduğu için, \sqrt{\pi} sayısı inşa edilebilir olurdu. Eğer ikinci problemi çözebiliyor olsaydık, \sqrt[3]{2} sayısı inşa edilebilir olurdu. Eğer üçüncü problemi çözebiliyor olsaydık, altmış dereceyi üçe bölerek yirmi dereceyi elde edebiliyor olurduk ve bunun sonucunda da cos(\frac{\pi}{9}) sayısı inşa edilebilir olurdu.

Öte yandan  bu sayıların hiçbiri, bir önceki bölümde gördüğümüz teorem gereği, inşa edilebilir değildir. Dolayısıyla bu problemleri pergel ve cetvel kullanarak çözemeyiz. Peki bu sayılar neden önceki bölümde gördüğümüz teoremdeki inşa edilebilirlik koşulunu sağlamıyorlar?

Bu yazıyı planlarken bu bölüm için ne yapacağımı kestirememiştim, yazarken belki aklıma bir şeyler gelir umuduyla bodoslama yazmaya giriştim. Düşündüm, taşındım ve kanaat getirdim ki bu sayıların neden teoremdeki inşa edilebilirlik koşulunu sağlamadığını geniş halk kitlelerine temel cisim kuramı kavramlarını göstermeden anlatmak için bir yol yok.

Dolayısıyla bu noktada kaçınılmaz olandan kaçmayı bırakıp sizi otorite etkisine maruz bırakacağım. Bu sayıların hiçbiri inşa edilemezler çünkü değiller! Eğer bu sayıların neden yukarıdaki teoremdeki inşa edilebilirlik koşulunu sağlamadığını öğrenmeyi kafaya koyduysanız lisans seviyesinde cisim genişlemelerini anlatan herhangi bir soyut cebir kitabı sizin için yeterli olacaktır. Anahtar kelimeyi veriyorum: Minimal polinomlar.

Carl Friedrich Gauss ile Neşeli Saatler’de bu hafta: Düzgün çokgen çizmek

Yazının bu son bölümünde bir düzgün çokgenin pergel ve cetvelle ne zaman inşa edilebileceğini öğreneceğiz.

Eğer pergel ve cetvel kullanarak bir düzgün n-gen çizebiliyorsanız  bu durumda \frac{2\pi}{n} açısı, dolayısıyla da cos(\frac{2\pi}{n}) sayısı inşa edilebilir olmalı. Bunun tersi de doğru. Eğer cos(\frac{2\pi}{n}) sayısı inşa edilebilirse, bu durumda pergel ve cetvelle düzgün bir n-gen çizilebilir. Bu iddiaların kanıtları çok zor olmadığı için egzersiz olarak okuyucuya bırakıyorum.

Demek ki bir düzgün çokgenin pergel ve cetvelle inşa edilip edilemeyeceğini belirleyen şey cos(\frac{2\pi}{n}) sayısının inşa edilebilirliği.

Büyük insan Carl Friedrich Gauss henüz on dokuz yaşındayken bir düzgün 17-genin pergel ve cetvelle çizilebileceğini kanıtlıyor. Günlüğüne göre Gauss’u matematikçi olmaya iten temel sebeplerden biri de Antik Yunan’dan beri bilinen ve o zamana kadar çözülemeyen bu soruyu çözmüş olması. Hatta Gauss bu sonucunu o kadar seviyor ki mezartaşına bir 17-gen çizilmesini istiyor ama taş ustası bunun zorluğunu ve çizilse bile çembere yakın bir görüntü ortaya çıkacağını söyleyerek bunu yapmayı reddediyor.

Yukarıda inşa edilebilir sayıların rasyonel sayılarla başlayıp her adımda önceki adımlarda elde ettiğimiz sayılara aritmetik işlemler ve karekök işlemi uygulayarak elde edebileceğimiz sayılar olduğunu gördük. Eğer düzgün 17-gen pergel ve cetvelle inşa edilebilir bir çokgense, cos(\frac{2\pi}{17}) sayısı inşa edilebilir bir sayı olacağından bu şekilde elde edilebilmeli. cos(\frac{2\pi}{17}) değerinin ne olduğunu görmek istiyorsanız ilgili Wikipedia sayfasına bakabilirsiniz.

Şimdi de bir düzgün çokgenin pergel ve cetvelle ne zaman inşa edilebileceğini karakterize eden genel teoremi görelim.

Teorem (Gauss-Wantzel): n \geq 3 olmak üzere, bir düzgün n-gen pergel ve cetvelle inşa edilebilirdir ancak ve ancak n sayısı ya ikinin bir kuvvetiyse ya da asal çarpanlarına ayrıldığında farklı Fermat asalları p_1,\dots,p_t için n=2^k p_1 \dots p_t formundaysa.

Gauss ünlü kitabı Disquisitiones Arithmeticae‘da teoremdeki koşulun bir düzgün çokgenin pergel ve cetvelle çizilebilmesi için yeterli olduğunu kanıtlıyor. Bu koşulun gerekli olduğunu söylese de bunun kanıtını vermiyor. İlgili koşulun gerekli olduğunun kanıtı da daha sonra Pierre Wantzel tarafından veriliyor.

Yazıyı noktalarken pergel ve cetvelle nasıl düzgün 5-gen ve 17-gen inşa edilebileceğini gösteren iki tane .gif dosyası  paylaşmak istiyorum.

C.N.

pentagon_construct

Düzgün beşgen inşası

regular_heptadecagon_inscribed_in_a_circle

Düzgün on yedigen inşası

[GM. 1] Dr. Garip Entropi veya: Nasıl kaygılanmayı bırakıp algoritmik rastgeleliği sevmeyi öğrendim

GM serisinin bu yazısında rastgelelik ve karmaşıklık kavramlarını irdeleyeceğiz. Bu gönderinin amacı -sahip olduğumuz rastgelelik sezgisini bence en iyi şekilde biçimselleştiren- Kolmogorov karmaşıklığının ne olduğunu anlamak.

Kolmogorov karmaşıklığına ara sıra algoritmik entropi ya da algoritmik karmaşıklık denildiği de oluyor. Dr. Strangelove filmine gönderme yapan başlıktaki entropi kelimesi de buradan devşirme.

Rastgelelik nedir?

Eminim ki şu ana kadar denk geldiğiniz pek çok teizm-ateizm odaklı tartışmada “hiç böyle muntazam bir düzen rastgele oluşmuş olabilir mi” veya “buradaki mekanizmalar tesadüfen oluşmuş, şuradaki moleküller de rastgele dizilmiş” şeklinde sözler duymuşsunuzdur. Böyle lafların edildiği bir tartışmaya tekrar denk gelirseniz, sizden ricam şu basit soruyu sorun: Rastgelelik nedir ve rastgele olduğunu ya da olmadığını iddia ettiğimiz objelerin rastgeleliğini hangi ölçüte göre belirliyoruz?

Bu soruya yanıt alamamanız çok olası. Bunu “yukarıdakileri söyleyen insanlar çoğunlukla ne hakkında konuştuğunu bilmeyen şuursuzlar” demek için söylemiyorum. Tamam, dürüst olayım; aslında biraz bunu ima etmek için söylüyorum. Ama varmak istediğim nokta bu değil. Bu soru, eğer daha önce üzerine hiç düşünmediyseniz ya da araştırma yapmadıysanız, cevaplaması kolay bir soru değil. Bu blog gönderisinde bu soruyu cevaplayacağız!

Rastgelelik nedir sorusunu cevaplamaya çalışmadan önce neyin rastgele olup olmadığı hakkında konuşacağımızı belirlemeliyiz. Bu yazıda bir karakter dizisinin rastgeleliği için bir ölçüt bulmaya çalışacağız. Günlük hayatta karşılaştığımız çoğu şeyi -genel olarak bilgiyi- karakter dizilerine kodlayabildiğimiz için yapacağımız tanım bize oldukça geniş bir oyun alanı sağlayacak.

Şimdi bir alfabe sabitleyelim. Burada alfabe ile kastettiğim şey en az iki elemanı olan herhangi bir sonlu sembol kümesi. Bu sembol kümesini Türkçe alfabesi, \{0,1\} kümesi ya da canınızın istediği herhangi bir sonlu küme seçebilirsiniz. Yazının geri kalanında yapacağımız tanımlar herhangi bir alfabe üzerine yapılabilir. Kolaylık olması açısından şimdilik alfabemizi Hint-Arap rakamları olan \{0,1,2,3,4,5,6,7,8,9\} kümesi olarak belirleyelim. Bundan sonra, aksi belirtilene kadar, karakterleri bu küme içerisinden seçilmiş sonlu karakter dizileriyle ilgileneceğiz.

Rastgelelik sezgimizi biçimselleştirmek

Rastgelelik nedir sorusuna anlamlı bir şekilde cevap verebilmek istiyorsak rastgeleliğe ölçüt olarak sunacağımız şeylerin sahip olduğumuz rastgele sezgisinin özünü olabildiğince yakalaması lazım. Bu noktada küçük bir deney yapmak faydalı olabilir. Aşağıdaki karakter dizilerinden hangileri diğerlerine göre daha rastgeledir?

a. 010101010101010101010
b. 0100100001000000001
c. 01101010001010001010
d. 01010011010101100101

Sanırım herkes a dizisinin rastgele olmadığına katılacaktır. Biraz dikkatli bakınca b dizisinin rastgele olmadığı da görülebilir. Önce bir tane 0 sembolü, arkasından 1 sembolü, sonra iki tane 0 sembolü, arkasından 1 sembolü, sonra dört tane 0 sembolü, arkasından 1 sembolü… Peki c dizisi? Biraz dikkatle bakarsanız c dizisinin [1,20]  aralığındaki asal sayıları temsil ettiğini görebilirsiniz. Asal sayılara denk gelen indislere 1, asal olmayan indislereyse 0 konulmuş. İlk başta gözümüze çarpmamıştı ama görünüşe göre c dizisi de rastgele değil. Geriye tek şık d kalıyor. Demek ki cevap d olmalı!

Peki ya d dizisi de bir şeyleri temsil ediyorsa da biz farkına varamıyorsak? Olabilir. Doğruyu söylemek gerekirse d şıkkını tuşlara kafama göre basarak oluşturdum. Eğer illa d dizisini verecek bir kural arıyorsanız hemen bir tane kural üretebiliriz. Aynı c dizisinin bir ve yirmi arasındaki asal sayıları kodlaması gibi, d dizisi de şurada gördüğünüz onuncu derece polinomun gerçel köklerini kodluyor. Ama bu polinomun kendisi de yukarıdaki dizi kadar rastgele değil mi? Ne biçim katsayılar onlar öyle?! Hmm… Bence cevabı d olarak işaretlemeliyiz. Öte yandan ortada d dizisini veren bir kural da var.

Belki de soruyu değiştirmeliyiz. Yeni bir soru soralım. Yukarıdaki karakter dizilerini “rastgelelik derecelerine” göre sıralayınız.

Bu sefer cevabın a<b<c<d olması gerektiğinde sanırım hemfikiriz. Zira az önce gördüğümüz üzere sezgimiz bir şeyin rastgele olup olmadığına karar verirken sadece bir kural olup olmadığına değil, aynı zamanda o kuralın ne kadar karmaşık olduğuna da bakıyor. Bu küçük deney vasıtasıyla yapacağımız rastgelelik tanımına dair iki önemli kavram izole ettik: Kurallı olmak ve bu kuralın karmaşıklığı.

Kurallı olmak dediğimiz şey ne ola ki? Bir karakter dizisinin kurallı olması ne demek? Bu karakter dizisini üreten iyi tanımlanmış bir prosedür (bir algoritma) olması demek. Peki sahip olduğumuz algoritma sezgisini matematiksel olarak nasıl modelleyebiliriz?

Hesaplanabilirlik, algoritmalar ve Church-Turing tezi

Az önce sorduğumuz soru hakkında tuğla gibi kitaplar yazılmış bir soru. Bu yazının anlaşılabilmesi için tüm bunları bilmek bir önem teşkil etmediğinden dolayı sadece merak edenlerin araştırabilmesi adına anahtar kelimeleri vererek özet geçeceğim. İşin 1900 öncesine giden kısmını tamamen atlıyorum.

  • Sene 1928. David Hilbert ünlü karar verme problemini ortaya atıyor. Soruyu cevaplayabilmek için haliyle insanların algoritma kavramını biçimselleştirmesi gerekiyor.
  • Sene 1931. Kurt Gödel, ünlü eksiklik teoremini kanıtlarken ilkel özyinelemeli fonksiyonları kullanıyor. Gödel, tanımladığı ilkel özyinelemeli fonksiyonların algoritma sezgimizi tamamen yakalamadığının farkına varınca, Jacques Herbrand‘ın da katkılarıyla beraber, 1934’te genel özyinelemeli fonksiyonlar ortaya çıkıyor. Daha sonra Stephen Kleene olaya müdahil olacak ve bugün \mu özyinelemeli fonksiyonlar dediğimiz fonksiyon sınıfını ortaya atacak, ki bu sınıftaki tam fonksiyonlar genel özyinelemeli fonksiyonlarla örtüşüyor.
  • Tüm bunlar olurken 1936’da Alonzo Church efendi “\lambda calculus çok güzel, siz de gelsenize” diyerek yeni bir hesaplanabilirlik modeli ortaya atıyor.
  • Sene 1936. Alan Turing doktora tez danışmanı olan Church’un modeline “Senin yapacağın \beta -indirgemesini şirinleyeyim” diye atarlandıktan sonra çığır açan makalesinde Turing makinelerini tanımlıyor. Aynı makalede karar verme problemini çözüyor ve Gödel’in teoreminin -daha farklı halinin- bir kanıtını veriyor. Bunları yaparken ortaya attığı evrensel Turing makinesi kavramı da on yıl içerisinde –John von Neumann‘ın da katkılarıyla- ilk bilgisayarlara dönüşmeye başlayacak.
  • Sene hala 1936. Emil Post, Turing’den bağımsız olarak Turing’inkine çok benzer bir hesaplanabilirlik modeli ortaya atıyor.

(Not: Bu hikayedeki kişiler ve olaylar tamamen gerçek, diyaloglarsa hayalidir.)

Bu insanların hepsi sahip olduğumuz algoritma sezgisinin kendilerinin ortaya attıkları matematiksel modellere karşılık geldiğini söylüyorlar. Sonra ne oluyor? Hesaplanabilirlik kavramını biçimselleştiren tüm bu matematiksel modellerin birbirine denk olduğu ortaya çıkıyor. Yani birinde hesaplanabilir olan her şey diğerlerinde de hesaplanabilir.

Şimdi elimizdekilere bir bakalım. Tüm bu dehaların algoritma sezgimizi biçimselleştirmek için ortaya attığı farklı matematiksel modellerin hepsi birbirine denk. Bu matematiksel modellerin neden algoritma sezgimize karşılık gelmesi gerektiğine dair ikna edici sezgisel argümanlar da var. O zaman algoritma sezgimiz gerçekten de bu matematiksel modellerde ortaya atılan şeye denk geliyor olmalı!

Bu son cümledeki iddiayı alıp bir metatez haline getirdikten sonra da ismini Church-Turing tezi koyuyoruz. Tek cümlede özetlemek gerekirse: Algoritma demek Turing makinesi demek, Turing makinesi demek algoritma demek.

Kolmogorov karmaşıklığı nedir?

Bir önceki bölümde gördük ki, sahip olduğumuz algoritma sezgisini Turing makineleriyle biçimselleştirebiliyoruz. Dolayısıyla Turing makinelerini kullanarak bir karakter dizisinin kurallı olmasından bahsedebiliriz. Ancak her sonlu karakter dizisini çıktı olarak üretebilecek bir Turing makinesi bulunabilir. Öte yandan bizim için önemli olan sadece bir kuralın olması değil, basit bir kuralın olmasıydı. Bir karakter dizisini üreten kuralın ne kadar basit olduğunu pekala onu üreten Turing makinesinin ne kadar karmaşık olduğu üzerinden ölçebiliriz. Peki Turing makinelerinin karmaşıklıklarını nasıl ölçeceğiz?

Hatırlayın, Turing efendi evrensel Turing makinesi diye bir şey bulmuştu. Evrensel Turing makineleri, gerekli girdi verildiği zaman, diğer tüm Turing makinelerini taklit edebilen Turing makineleridir. O zaman, bir evrensel Turing makinesi sabitledikten sonra, bir karakter dizisinin rastgeleliğini onu üreten Turing makinesinin ilgili evrensel Turing makinesine göre kodunun uzunluğu olarak tanımlayabiliriz.

Farkındayım, son cümleyle ortalığı çok bulandırdım. Bu yazının [GM] serisinin bir parçası olarak geniş halk kitleleri için tasarlanmış olması gerekmiyor mu?

Bu noktada evrensel Turing makinelerini ve Kolmogorov karmaşıklığının matematiksel literatürdeki asıl tanımını bir kenara bırakacağım. Amacımız rastgeleliğin ne olduğunu anlamak, konuyla ilgili akademik makale yazmak değil. Bu yüzden, yazının geri kalanında anlatacağım her şeyi gerçek bir programlama dili üzerinde yapacağım.

Öte yandan, konuyla akademik olarak ilgilenmek isteyen ve aşağıda yapacağım tanımların matematiksel olarak doğru ifadelerini merak edenler olursa diye not düşeyim. Bu konuyu öğrenebileceğiniz temel kaynaklarından biri Algorithmic Randomness and Complexity kitabıdır.

Her neyse. Olabildiğince geniş bir halk kitlesine seslenebilmek adına içerisinde çalışacağımız programlama dilini C olarak seçiyorum. Bu seçimin bir sonucu olarak da bundan sonra karakter dizilerimizin sembollerinin içerisinden seçildiği alfabe sadece Hint-Arap rakamları kümesi değil, bu dilde çıktı olarak üretebileceğimiz tüm semboller kümesi olacak.

Aşağıda yapacağımız tanımların hepsini favori programlama dilinize kolayca genelleyebilirsiniz. Yapacağımız kanıtlar da sadece dilin çıktı üretmek ve döngü gibi temel fonksiyonlarını kullanacağından dolayı, ilgili kanıtların favori programlama dilinize aktarılmasını size egzersiz olarak bırakıyorum.

İşlerimizi kolaylaştırmak için programlama dilimizle ilgili -gerçek hayatta geçerli olmayan- birkaç varsayımlarda bulunacağız.

  • Birinci olarak, programlama dilimizdeki programların kullanıcıdan girdi almadığını varsayacağız. Bu varsayım ilk başta saçma gözükebilir. Öte yandan, bir program+girdi ikilisi verildiğinde, ilgili girdiyi programın kaynak koduna hard-coded bir şekilde ekleyerek mevzubahis program+girdi ikilisiyle aynı işi gerçekleştiren ve kullanıcıdan girdi almayan başka bir program üretebiliriz. Demek ki programlarımızın girdi almadığını kabul etmemizde bir sakınca yok.
  • İkinci olarak, bilgisayarımızın hafızasının sınırsız olduğunu varsayacağız. Matematik yapıyoruz şurada; evrendeki parçacık sayısı sınırlı diye teorem kanıtlamayacak değiliz ya?!
  • Son olarak, programlama dilimizdeki değişkenlerin sınırsız büyüklükte değerler tutabildiğini varsayacağız. Lafın gelişi, int tipindeki bir değişken aldığımızda, bu değişken sınırsız büyüklükte tam sayıları taşma olmadan tutabilecek.

Şimdi yazının ana konusu olan Kolmogorov karmaşıklığını tanımlamaya hazırız.

Tanım: Bir w dizisinin Kolmogorov karmaşıklığı w dizisini çıktı olarak üreten en kısa programın kaynak kodunun uzunluğudur. Bundan sonra w dizisinin Kolmogorov karmaşıklığını K(w) ile göstereceğiz.

Üzerine biraz düşündüğünüzde, bu tanımın rastgelelik sezgimizle ne kadar örtüştüğünü görebilirsiniz. Bir diziyi üreten en kısa program (kural) ne kadar uzunsa (ne kadar karmaşıksa) o dizi algoritmik olarak o kadar karmaşıktır. Bir dizi algoritmik olarak ne kadar karmaşıksa, o kadar rastgeledir!

Bu noktada yaptığımız tanıma yapılabilecek bariz bir itiraz var. Eğer başka bir programlama dili kullanıyor olsaydık, karakter dizilerinin Kolmogorov karmaşıklıkları değişecekti. Bu durumda bir karakter dizisinin olası her programlama dili için ayrı bir Kolmogorov karmaşıklığı olacaktır. Bu eleştiride sonuna kadar haklısınız. Öte yandan, içerisinde çalıştığınız diller Turing-tam olduğu -yani bir evrensel Turing makinesini simüle edebildiği- sürece aşağıdaki teorem geçerli.

Teorem: K ve K' verilen iki Turing-tam programlama dili için ilgili Kolmogorov karmaşıklıklarını veren fonksiyonlar olsun. Bu durumda öyle bir c sabiti vardır ki her w dizisi için K(w) \leq K'(w) +c olur.

Yani bir programlama dilinden diğerine sıçradığımızda dizilerin Kolmogorov karmaşıklıkları en fazla -bu iki dile bağlı- bir sabit kadar değişebilir. Bunun anlamı da şu, karakter dizilerinin uzunlukları ve Kolmogorov karmaşıklıkları arasındaki ilişki, yeterince uzun karakter dizilerini göz önüne aldığımızda, içerisinde çalıştığımız programlama dilini değiştirmemizden fazla etkilenmeyecek. Dolayısıyla yaptığımız tanımın programlama diline bağımlılığı o kadar ciddi bir sorun değil.

Şimdi Kolmogorov karmaşıklığıyla ilgili basit bir gerçeği görelim . Her w dizisi için w dizisinin uzunluğunu |w| ile gösterelim.

Teorem: Her w dizisi için K(w) \leq |w|+36.
Kanıt: Bir w dizisi alalım. Bu durumda

#include<stdio.h>
main(){printf(“w“);}

programı çıktı olarak w üretecektir. Burada w gösterimi ile kastedilen şey, programın kaynak kodunda w dizisini hard-coded bir şekilde eklememiz. Yani programımız çıktı olarak ürettiği karakter dizisinin kendisini kaynak kodun içerisinde barındırıyor. Bu programın uzunluğu |w|+36 olduğuna göre K(w) \leq |w|+36 olmak zorunda. \blacksquare

Aynen yazının başında yaptığımız deneyde d şıkkındaki karakter dizisini bir polinomun kökleri olarak hard-code ettiğimiz gibi, herhangi bir karakter dizisini o karakter dizinden en fazla 36 karakter daha uzun bir programla üretebiliyoruz. Dolayısıyla w dizinin ne kadar rastgele olduğuna, K(w) değerinin |w| değerine ne kadar yakın olduğuna bakarak karar vereceğiz.

Mesela w dizi olarak \pi sayısının ilk 800 basamağı seçelim. Bu durumda |w|=800 olduğu halde K(w) \leq 160 olacaktır zira aşağıdaki program \pi sayısının ilk 800 basamağını üretiyor.

int a=10000,b,c=2800,d,e,f[2801],g;main(){for(;b-c;)f[b++]=a/5; for(;d=0,g=c*2;c-=14,printf(“%.4d”,e+d/a),e=d%a)for(b=c;d+=f[b]*a, f[b]=d%–g,d/=g–,–b;d*=b);}

Bu program şuradan alıntı. Bu karakter dizisini belki daha kısa bir programla üretmek de mümkündür. Bilmiyorum. Önemli olan zaten K(w) değerinin ne olduğu değil, |w| değerine oranla ne kadar küçük olduğu. Bu değerler arasındaki fark bize \pi sayısının ilk 800 basamağının algoritmik olarak rastgele olmaktan ne kadar uzak olduğunu söylüyor.

Buna karşın, mesela, 800 kere yazı-tura atarak sembolleri 0 ya da 1 olan bir karakter dizisi oluşturursam, bu durumda K(w) değeri büyük ihtimalle 800’e yakın bir şey olacaktır. Niye büyük ihtimalle diyorum?

Eğer az önce gerçekten de 800 kere yazı-tura atıp bir karakter dizisi üretmiş olsaydım, yazıp çizip üzerine düşündükten sonra K(w) değerinin ne olduğunu hesaplayamaz mıydım?

Kolmogorov karmaşıklığının hesaplanamazlığı

Yazının bu bölümünde hayatın acımasız gerçeklerinden biriyle karşılaşacağız: K(w) fonksiyonu hesaplanamaz bir fonksiyon. Yani öyle bir algoritma bulamam ki kendisine girdi olarak bir w dizisi verildiğinde, çıktı olarak K(w) değerini üretsin.

Bu noktada üzerine basa basa vurgulama gereği duyuyorum. Hiçbir dizinin Kolmogorov karmaşıklığının hesaplanamayacağını söylemiyorum. Çeşitli spesifik dizilerin Kolmogorov karmaşıklıkları bulunabilir. Söylediğim şey, her dizinin Kolmogorov karmaşıklığını hesaplayacak bir algoritma olmadığı. Bunun kanıtını az sonra hep birlikte göreceğiz.


Kanıta geçmeden önce Bertrand Russell‘ın kütüphaneci G. G. Berry’ye atfettiği Berry paradoksundan bahsetmek istiyorum. Şu cümleye bakalım.

On iki kelimeden daha az kelimeyle tanımlanamayan en küçük doğal sayı.

Dilimizde sonlu tane kelime olduğuna göre en fazla on bir kelimeyle tanımlanabilen sonlu tane doğal sayı vardır. Bu durumda, sonsuz tane doğal sayı olduğuna göre, on iki kelimeden daha az kelimeyle tanımlanamayan doğal sayılar olmak zorunda. Dolayısıyla bunların en küçüğü de vardır. Öte yandan bu doğal sayıyı yukarıdaki ifadeyi kullanarak on bir kelime ile tanımladık. Çelişki.

Peki ortadaki sıkıntının kaynağı ne? Ortadaki sıkıntının kaynağı “tanımlanamayan” kelimesindeki belirsizlik. Zira bu kelimeyi kullanarak -üstü kapalı bir biçimde- dilimizdeki ifadelerin her birinin bir doğal sayı tanımlayıp tanımlamadığına karar verebileceğimizi varsayıyoruz. Öte yandan bu doğru değil. Mesela şu ifadeye bakalım.

Eğer ‘Bu cümle yanlıştır.’ cümlesi doğruysa birden büyük en küçük doğal sayı, değilse birden küçük en büyük doğal sayı

Bu ifade hangi doğal sayıyı tanımlıyor, iki sayısını mı sıfır sayısını mı? Bu ifade bir doğal sayı tanımlamıyor zira bu ifadenin tanımladığı doğal sayının ne olduğuna karar vermeye çalıştığımızda yalancı paradoksu suratımıza bir tokat gibi çarpıyor.


Şimdi Kolmogorov karmaşıklığının hesaplanamazlığının kanıtına geçebiliriz. Kanıtın ana fikri Berry paradoksunu taklit etmek olacak. Eğer Kolmogorov karmaşıklığı hesaplanabiliyor olsaydı, bu durumda Berry paradoksuna benzer bir çelişki kanıtlayabileceğimizi göreceğiz.

Teorem: Öyle bir program yoktur ki kendisine girdi olarak verilen her w dizisi için çıktı olarak K(w) değerini üretsin.
Kanıt: Kanıtı olmayana ergi yöntemi ile yapacağız. Varsayalım ki Kolmogorov karmaşıklığını hesaplayan bir program yazabiliyoruz. Bu durumda, bu programı kullanarak öyle bir kolmogorov() fonksiyonu yazabiliriz ki bu fonksiyon kendisine verilen her tam sayı i değeri için alfabetik olarak i. sıradaki karakter dizisinin Kolmogorov karmaşıklığını döner. Şimdi şu kod parçasına bakalım.

#include<stdio.h>
[Burada kolmogorov() fonksiyonu olacak]
main()
{
int i;
for(i=0;;i++) if(kolmogorov(i)>k) {printf(“%d”,i); break;}
}

Burada k dediğimiz şey kaynak kodun içerisine elle girilmiş bir doğal sayı olacak. Hangi k değerinin kullanılması gerektiğini az sonra göreceğiz.

Bu programın ne yaptığı açık olmalı. Bir döngü vasıtasıyla i=0’dan itibaren alfabetik olarak i. sıradaki karakter dizisinin Kolmogorov karmaşıklığını hesaplıyor, eğer bu değer programa girilen k değerinden büyükse çıktı olarak bu karakter dizisini üretip duruyor. Yani bu program bize Kolmogorov karmaşıklığı k sayısından büyük olan alfabetik olarak ilk karakter dizisini veriyor.

Bu kaynak kodun k değerinin yazıldığı yer hariç uzunluğuna N diyelim. Polinomlar logaritmik fonksiyonlardan hızlı büyüdüğü için öyle bir k değeri bulabiliriz ki

k > N+log_{10}(k)+1

olur. Şimdi bu eşitsizliği sağlayan bir k değerini alıp programdaki k yerine yazarak programı çalıştıralım. Bu programın çıktısı ne olacak?

Kolmogorov karmaşıklığı k sayısından daha büyük bir dizi. Peki bu diziyi çıktı olarak üreten yazdığımız bu programın uzunluğu ne? Seçtiğimiz k sayısını programda k yerine yazarken  \lfloor log_{10}(k) \rfloor+1 sembol kullanacağımıza göre

N+ \lfloor log_{10}(k) \rfloor+1 .

Ancak biliyoruz ki k > N+log_{10}(k)+1 . Demek ki az önce kendisini üreten en kısa programın uzunluğu k+1 olan bir karakter dizisini, uzunluğu k sayısından daha küçük bir programla ürettik. Çelişki. Demek ki böyle bir kolmogorov() fonksiyonu yazılamaz. Demek ki kanıtın başında yaptığımız varsayım yanlış olmalı. \blacksquare

Görüldüğü üzere Kolmogorov karmaşıklığını algoritmik yöntemlerle hesaplayamıyoruz. Aksi takdirde Kolmogorov karmaşıklığını hesaplayan algoritmadan bu algoritmanın kendi uzunluğundan daha büyük Kolmogorov karmaşıklığına sahip bir karakter dizisini hesaplamasını isteyerek çelişki yaratabilirdik. Bu durumda da evren birdenbire yok olurdu!

Aslında yukarıda kanıtladığımızdan çok daha fazlası doğru. Kolmogorov karmaşıklığı kavramını velet yaşında kendi başına keşfedip, bunu her kitabında üstüne basarak vurgulayan yedi cihanın pek egomanyak matematikçilerinden Gregory Chaitin‘in konuyla ilgili bir eksiklik teoremi var.

Bu teorem kabaca şunu söylüyor. Belirli özellikleri sağlayan bir belitsel sistem aldığımızda öyle bir L sabiti bulabiliriz ki belitsel sistemimiz hiçbir w dizisi için K(w) \geq L olduğunu kanıtlayamaz. Buradaki “belirli özellikler” kısmının ne olduğuna girmeyeceğim zira bu koşulların ne olduğunu çarpıtmadan anlatabilmek için fazla teknik konulara girmem lazım. Bu tarz bir işe [GM] serisinde girmeye niyetli değilim. Öte yandan şunu bilin. Eğer bugün içerisinde çalıştığımız matematiksel sistem çelişkisizse ve yanlış önermeler kanıtlamıyorsa, öyle bir L sabiti bulabiliriz ki, Kolmogorov karmaşıklığı L ‘den büyük olan karakter dizileri olduğunu bildiğimiz halde herhangi bir spesifik karakter dizisinin Kolmogorov karmaşıklığının L ‘den büyük olduğunu kanıtlayamayız.

Yazının bir sonraki bölümüne geçmeden önce Kolmogorov karmaşıklığının hesaplanamazlığını kullanarak durma probleminin çözümsüzlüğünü de kanıtlamayı planlıyordum ama zaten gereğinden fazla uzayan bu yazıyı bir an önce bitirmek adına  bu kanıtın sadece taslağını verip bırakacağım.

Diyelim ki öyle bir M programı var ki bu program kendisine verilen bir kaynak kodun ürettiği programın durup durmayacağına sonlu adımda karar verebiliyor. Bu durumda  M programını kullanarak Kolmogorov karmaşıklığını hesaplayan bir algoritma yazabiliriz. Verilen bir  w  için  K(w) \leq |w|+36  olduğunu biliyoruz. Uzunluğu en fazla bu üst sınır kadar olan tüm programları -ki böyle sonlu tane program var- sırasıyla listeleyebiliriz. Daha sonra M programını kullanarak bu programların hangilerinin durup durmayacağına karar verebiliriz. Duran programların hangileri olduğuna karar verdikten sonra, tüm bu programları sırasıyla çalıştırabiliriz. Bu programların sonlu adım sonunda duracaklar. Hepsi durduktan sonra w  çıktısını üreten en kısa programın uzunluğunu ve dolayısıyla K(w) değerini kolayca hesaplayabiliriz. Öte yandan, K(w)‘nin hesaplanamaz bir fonksiyon olması gerektiğini biliyoruz. Demek ki kendisine verilen programların durup durmayacağına karar verebilecek yukarıdaki gibi bir M programı olamaz.

Algoritmik rastgelelik

Bu yazıdaki ana amacımız rastgelelik sezgimizle örtüşen matematiksel bir tanım bularak şeylerin ne kadar rastgele olduğuna karar vermekti. Kolmogorov karmaşıklığının ne olduğunu öğrendiğimize göre bu kavramı kullanarak bir rastgelelik tanımı yapabiliriz.

Bir w karakter dizisi algoritmik olarak rastgeledir ancak ve ancak K(w) \geq |w| ise. Yani bir karakter dizisi algoritmik olarak rastgeledir ancak ve ancak bu karakter dizisini çıktı olarak üretecek her programın kaynak kodu en az bu karakter dizisinin kendisi kadar bilgi barındırmak zorundaysa. Bu tanıma göre bir karakter dizisinin rastgele olması, bir anlamda bu dizinin sıkıştırılamaz olduğunu söylüyor.

Peki algoritmik olarak rastgele diziler var mıdır? Belirli bir uzunluktaki olası tüm karakter dizilerinin sayısını ve olası tüm kaynak kodların sayısını karşılaştırarak algoritmik olarak rastgele dizilerin var olması gerektiğini kolayca kanıtlayabilirsiniz. Okuyucuya egzersiz olsun bu.

Yazıyı noktalarken küçük birkaç not düşeyim. Yukarıdaki tanım altında kısa karakter dizilerinin çoğunun algoritmik olarak rastgele olduğunu göreceksiniz. Lafın gelişi, 01010101 dizisini üretmek için de 71214527 dizisini üretmek için de en kısa yol bu karakter dizilerini kaynak koda ekleyerek bastırmak. Biz bu dizilere baktığımızda 01010101 dizisinde 71214527 olmayan bariz bir kural görüyoruz. Öte yandan bu kuralı algoritmik olarak ifade etmek -dört kere dönen bir döngü yaratmak ve döngünün her dönüşünde 01 dizisini bastırmak- dizinin kendisini kaynak koda eklemekten daha pahalıya mal olacağı için, birinci dizide bariz bir kuralın olması onu ikinci diziden daha az rastgele yapmayacak.

Dolayısıyla, yaptığımız algoritmik rastgelelik tanımı kısa karakter dizilerinde -eğer gözlemlediğimiz kuralı algoritmik olarak ifade etmek en az dizinin kendisi kadar bilgi gerektiriyorsa- her zaman umduğumuz gibi sonuç vermeyebilir. Bununla birlikte, ilgilendiğimiz karakter dizilerinin uzunlukları arttıkça sezgisel olarak beklediğimiz şeye yakın sonuçlar alacağız.

Son olarak da Kolmogorov karmaşıklığını kullanarak sonsuz karakter dizileri için algoritmik olarak rastgeleliği tanımlamanın mümkün olduğunu belirteyim.

C.N.

[GM. 0] Normal gerçel sayılar

GM serisinin bu ilk yazısında bilumum dizilerde ve filmlerde çeşitli efsanelere konu olan “içerisinde yazılabilecek her türlü sonlu sayısını dizisini barındıran” normal sayıları inceleyeceğiz.

Gerçel sayıların çeşitli tabanlarda gösterimleri

Çeşitli tarihi sebeplerle bugün gerçel sayıları ifade ederken \{0,1,2,\dots,9\} sembolleriyle onluk taban kullanıyoruz. Öte yandan kullandığımız sayı tabanını her zaman değiştirebiliriz. Mesela \{0,1,2\} sembolleriyle çalışıp üçlük taban kullanabiliriz. Bu durumda, lafın gelişi, \pi sayısı 10.010211012 \dots şeklinde ifade edilecektir.

Genel olarak, b \geq 2 olmak üzere, herhangi bir r pozitif gerçel sayısını s bir doğal sayı ve 0 \leq r_i < b tam sayılar olmak üzere

 r = s + \sum_{n=1}^{\infty} \frac{r_i}{b^n}

olarak ifade edebiliriz. Bu durumda

s.r_0 r_1 r_2 \dots

ifadesine r sayısının b -tabanında gösterimi diyelim. Negatif bir gerçel sayının b -tabanındaki temsilini de o sayının mutlak değerinin b -tabanındaki temsilinin önüne eksi işareti koyarak yapabiliriz.

Tabii bazı sayılar birden çok gösterime sahip olabilir. Mesela bir bölü üç sayısını üçlük sistemde 0.1000 \dots ya da 0.0222\dots olarak ifade edebiliriz. Benzer şekilde 1  sayısını onluk sistemde 1.000 \dots yerine 0.999 \dots olarak ifade edebiliriz.

Öte yandan bir gerçel sayının bir b -tabanında birden çok açılımı varsa, bu gerçel sayı en fazla iki açılıma sahiptir ve bu açılımlardan birisi bir noktadan sonra tamamen 0 olurken diğeri de bir noktadan sonra tamamen b-1 olacaktır. Bunun kısa bir kanıtına şuradaki math.stackexchange sorusundan erişilebilir. Daha sonrası için belirtmekte fayda görüyorum, aşağıda yapacağımız b-tabanında normallik tanımı için birden çok açılıma sahip sayıların hangi açılımını kullandığımız önemli olmayacak çünkü böyle sayılar zaten iki açılımlarına göre de b-tabanına göre normal olmayacaklar.

Gerçel sayıların gösterimlerine bilgi kodlamak

Belirli bir taban sabitleyelim. Alışkanlıklarımız gereği şimdilik on tabanını kullanalım. Şimdi \{0,1,2,\dots,9\} kümesinden sembollerle yazılabilecek olası her sonlu diziden oluşan kümeyi düşünün. Bu kümeye W_{10} diyelim.

W_{10} kümesi sayılabilir sonsuzluktadır. Dolayısıyla bu kümenin elemanlarını doğal sayılarla numaralandırarak listeleyebiliriz. Mesela bu kümedeki dizileri önce uzunluklarına göre, aynı uzunluktaki dizileri de kendi içerisinde “alfabetik” olarak listelersek karşımıza şöyle bir liste çıkacak.

0, 1, 2, 3, \dots, 9, 00, 01, \dots, 09, 10, 11, \dots, 19, 20, 21, \dots , 29, \dots, 39, \dots, 99, 000, 001, \dots

Burada “alfabetik” listeleme yapılırken karşılaştırmayı soldan yapıyoruz ve 0 sembolünün 1  sembolünden önce geldiği, 1 sembolünün 2 sembolünden önce geldiği, … varsayılıyor.

Şimdi basit bir soru soralım. Onluk sistemdeki gösterimi W_{10} kümesindeki her elemanı en az bir kere barındıran bir gerçel sayı var mıdır? Tabii ki.

0.012345678900010203040506070809101112131415 \dots

Yukarıda listelediğimiz tüm dizileri uçuca eklersek elde ettiğimiz sonsuz dizi bir r gerçel sayısının on tabanındaki gösterimi olmak zorunda. İnşası gereği r sayısının onluk tabandaki gösterimi \{0,1,2,\dots,9\} sembolleri ile yazılabilecek her sonlu diziyi içeriyor.

Demek ki buram buram mistisizm kokan çeşitli şehir efsanelerinde başrol oynayan “yazılabilecek olası tüm sayı kombinasyonlarını içermek” özelliği o kadar da ahım şahım bir özellikle değilmiş. Maharet olası tüm sayı kombinasyonlarını en az bir kere içermekte değil, bunu sonsuz kere ve eş dağılımlı olarak yapabilmekte. Eş dağılımın ne anlama geldiğini az sonra göreceğiz.

Daha zor bir soru

Yukarıdaki soru çok kolay oldu. Soruyu biraz daha zorlaştıralım. Öyle bir r gerçel sayısı bulabilir miyiz ki r sayısının onluk tabandaki gösterimi W_{10} kümesindeki her elemanı sonsuz defa içersin? Biraz düşünürseniz aslında yukarıda inşa ettiğimiz r gerçel sayısının bu özelliği sağladığını görebilirsiniz.

W_{10} kümesinin her elemanı oluşturduğumuz liste içerisinde sonsuz kere gözüküyor. Zira her sonlu dizi kendisinden daha uzun sonsuz tane sonlu dizinin alt dizisi olduğuna göre, tüm sonlu dizilerin r sayısının ondalık açılımında sonsuz kere gözüktüğü kanıtlanabilir. Mesela 01 dizisini 101, 201, \dots 901, 1001, 2001, \dots, 9001, \dots dizilerinin bir alt dizisi olarak liste içerisinde sonsuz kere göreceğiz. Demek ki daha zor gözüken bu soru da aslında o kadar zor değilmiş.

Şimdi soruyu iyice zorlaştıralım. Öyle bir r  gerçel sayısı bulabilir miyiz ki W_{10} kümesindeki her dizi r sayısının onluk tabandaki gösteriminde “dizi uzunluğuna göre eşit frekansta” gözüksün. Bu noktada “dizi uzunluğuna göre eşit frekans” ile ne kastettiğimi biraz açmam lazım.

f_r(w,n) fonksiyonu bize r  sayısının onluk tabanda gösteriminin ilk n  basamağı içerisinde w dizisi ile bir alt dizi olarak kaç kere karşılaştığımızı versin. Mesela yukarıda inşa ettiğimiz r sayısı için f_r(12,10)=1 olacaktır çünkü ilk on terim içerisinde 12 dizisi ile sadece bir kere karşılaşıyoruz. Dizi uzunluğuna göre eşit frekans ile kastettiğimiz şey de şu:

  • \{0,1,2,\dots,9\} kümesindeki her w elemanı için \lim_{n \rightarrow \infty} \frac{f_r(w,n)}{n} = \frac{1}{10} olsun.
  • \{00,01,02,\dots,10,11,\dots,90,\dots,99\} kümesindeki her w elemanı için \lim_{n \rightarrow \infty} \frac{f_r(w,n)}{n} = \frac{1}{100}  olsun.
  • Genel olarak, sembolleri \{0,1,2,\dots,9\} kümesinden seçilen k uzunluğundaki her w dizisi için \lim_{n \rightarrow \infty} \frac{f_r(w,n)}{n} = \frac{1}{10^k}  olsun. Yani sembolleri işbu küme içerisinden seçilerek oluşturulmuş her sonlu dizi, r sayısının ondalık açılımı içerisinde aynı uzunluğa sahip olan diğer sonlu dizilerle eşit frekansta gözüksün.

Eğer bir r gerçel sayısı bu özelliği sağlıyorsa, bu durumda r sayısına 10-tabanında normal sayı denir. On tabanında normal bir sayı örneği var mıdır? Şaşırtıcı ama tüm pozitif doğal sayıları on tabanında yazdıktan sonra art arda listeleyerek oluşturacağınız

0.12345678910111213141516171819 \dots

sayısı, ki kendisi Champernowne sabiti olarak bilinir, on tabanında normaldir. Şimdi biraz daha fantastik bir örnek görelim. Tüm asal sayıları on tabanında yazdıktan sonra art arda listeleyerek oluşturacağınız

0.235711131719 \dots

sayısı, ki kendisi Copeland-Erdös sabiti olarak bilinir, on tabanında normaldir.

Normal sayı nedir?

Yazının önceki bölümünde bir sayının on tabanında normal olmasının ne demek olduğunu tanımladık. Öte yandan yaptığımız tüm tanımları b \geq 2 olmak üzere başka bir b sayı tabanı için de yapabilirdik. Böylece b -tabanında normal olmaktan bahsedebilirdik. Tanımların b-tabanına nasıl genelleceği okuyucuya egzersiz olsun.

Eğer bir r gerçel sayısı her b \geq 2 tam sayısı için b -tabanında normalse, o sayıya normal sayı diyoruz.

Rasyonel sayıların bir tabana göre açılımları bir noktadan sonra ya tamamen sıfır olacağından ya da kendini periyodik olarak tekrarlayan sonlu bir diziden oluşacağından dolayı, rasyonel sayılar normal olamaz. Buradaki ilk iddianın on tabanı için kanıtı şurada var, diğer tabanlar için kanıt da benzer biçimde yapılabilir. Demek ki, eğer normal gerçel sayılar varsa, irrasyonel olmak zorundalar.

Peki irrasyonel olup da normal olmayan bir sayı bulabilir miyiz? Tabii ki. Mesela onluk tabandaki gösterimi

0.101001000100001000001 \dots

olan gerçel sayı -bırakın normal olmayı- on tabanında bile normal bir sayı değil. Zira onluk tabandaki açılımı içerisinde, mesela, 2 dizisini barındırmıyor. Benzer bir şekilde, onluk tabanda basamakları 9 rakamını içermeyen hiçbir sayı normal olamaz.

Az önce bir yığın normal olmayan sayı örneği gördük! Peki normal bir sayı örneği gösterebilir miyiz? Mesela yukarıda iki tane sabitten söz ettik ve ikisi de on tabanında normaldi. Peki bu sabitler diğer tabanlarda normal mi? Yani bu sayıları, lafın gelişi, 17-tabanında yazmaya kalksam ilgili alfabede yazılan her sonlu diziyi sayının 17-tabanındaki gösteriminde beklenen frekansta görecek miyim? Bu soruların cevabı bilinmiyor.

Bir sayının normal olduğunu göstermek zor bir iş. Elimizdeki örneklerin hepsi belirli tabanlar için özel olarak tasarlanmış yapay örnekler. Peki hiç mi normal sayı yok?

Endişe etmeyin, normal sayılar var. Mesela Chaitin sabitinin normal olduğu biliniyor. Öte yandan Chaitin sabiti, Turing makinelerinin durma olasılıkları üzerinden tanımlanabilse de, hesaplanamaz bir sayı olduğu için “bana basamaklarını listele” derseniz bunu algoritmik bir biçimde yapmak imkansız. Eğer hesaplanabilir bir normal sayı görmek isterseniz şu makale okunabilir. Makalenin dergide basılmış haline erişiminiz yoksa preprint haline şuradan da erişilebilir.

Normal sayılar her yerde

Normal sayıların var olduğunu gördük. Peki “ne kadar” normal sayı var? Normal sayılar kümesi sayılamaz sonsuzlukta, hatta tam olarak gerçel sayılarla aynı büyüklükte. Yani ne kadar gerçel sayı varsa o kadar normal sayı var. Eğer sayılamaz sonsuzlukta kümelere biraz haşır neşirseniz bunun o kadar da şaşırtıcı bir şey olmadığını fark etmeniz işten bile değil. Şimdi daha şaşırtıcı bir teoremi görelim.

Teorem (Émile Borel): Normal olmayan sayıların Lebesgue ölçümü sıfırdır.

Bu gönderi [GM.] kategorisinde olduğundan dolayı Lebesgue ölçümünün ne olduğunu tanımlamaya girişmeyeceğim. Öte yandan sezgisel olarak fikir vermesi açısından Lebesgue ölçümüyle ilgili birkaç kelam etmek istiyorum. Lebesgue ölçümü bize gerçel sayıların (ölçülebilir denen özel) alt kümelerinin ne kadar “uzun” olduğunu söyleyen bir ölçüm. Kısaca Lebesgue ölçümünü sezgisel olarak tek boyutta sahip olduğumuz “uzunluk” kavramının bir genellemesi olarak düşünebilirsiniz. Tabii sadece (a,b) formundaki aralıkların değil gerçel sayıların pek çok alt kümesinin “uzunluğunu” ölçmeye çalışıyoruz. Bu noktada Lebesgue ölçümüyle ilgili yazmayı bırakıp yukarıdaki teoremin çok ilginç bir sonucundan bahsedeyim.

Noktasal uçlu bir dart ile sayı avlamak

[0,1] aralığındaki her sayıyı, eğer sayı normalse kırmızıya, normal değilse maviye boyayalım. Şimdi sonsuz incelikte noktasal bir uca sahip bir dartı [0,1] aralığına fırlatalım. Dartın kırmızı bir noktaya isabet etme olasılığı kaçtır?

Borel’in yukarıda alıntıladığım teoreminin bir sonucu olarak bu sorunun cevabı 1 . Evet, yanlış duymadınız, eğer dartı rastgele fırlatıyorsanız -yani dartın bu aralıktaki noktalara çarpma olasılığını veren dağılım düzgünse- dartın normal olmayan bir sayıya isabet olma olasılığı 0 . Tabii ki şunu unutmamakta fayda var, sürekli bir olasılık dağılımından bahsettiğimiz için bir olayın olasılığının 0 olması o olayın olmayacağı anlamına gelmiyor.

Normal olmayan bir yığın sayı var. Hatta normal olmayan sayılar kümesinin büyüklüğü ile normal olan sayılar kümesinin büyüklükleri küme kuramı perspektifinden  bakıldığında aynı -ikisi de gerçel sayılar kümesiyle aynı kardinalitede. Öte yandan normal ve normal olmayan ikilemine ölçüm kuramı açısından yaklaştığımızda, normal sayılar kümesi normal olmayan sayılar kümesinden daha büyük ölçüme sahip. “Hemen hemen her sayı” normal bir sayı.

Demek ki, ölçüm kuramı perspektiften bakıldığında, asıl anormal olan normal olmamak. Bu noktada matematikçilerin içerisinde bulunduğu absürt bir durumu vurgulamakta fayda görüyorum. Hemen hemen her sayının normal olduğunu biliyoruz, yani dartımızı nereye atsak normal bir sayıya denk gelmemiz lazım. Ancak spesifik olarak normal olduğunu kanıtlayabildiğimiz fazla sayı yok. \pi, e, \dots gibi önemli sayıların normal olduğu düşünülüyor, ancak bunların hiçbirinin normal olduğu kanıtlanmış değil.

C.N.