Tekli sayı sistemi

Tekli sayı sistemi, doğal sayıları temsil eden en basit sayı sistemidir: bir N sayısını temsil etmek için, 1'i temsil eden bir simge N kez tekrarlanır.

Tekli sistemde, 0 (sıfır) sayısı boş diziyle, yani bir sembolün olmamasıyla temsil edilir. 1, 2, 3, 4, 5, 6, ... sayıları tekli sistemde 1, 11, 111, 1111, 11111, 111111, ... olarak temsil edilir.

Sayımda çetele tutulması, tekli sayı sisteminin bir uygulamasıdır. Örneğin, | çetele işaretini kullanarak 3 sayısı | | | şeklinde gösterilir. Doğu Asya kültürlerinde, 3 rakamı, üç fırça darbesiyle çizilen bir karakter olan 三 ile temsil edilir. (Bir ve iki sayıları da benzer şekilde temsil edilirler.) Çin ve Japonya'da 5 çizgi ile çizilmiş 正 karakteri bazen 5'in çeteleyle temsilinde kullanılır.

Tekli numaralar repunit numaralarla karıştırılmamalıdır. Her ikisi de tekrarlanan birler halinde yazılır ama ikincisi her zamanki ondalık sayısal çıkarıma sahiptir.

Operasyonlar 
Tekli sistemde toplama ve çıkarma basit dize birleştirmeden biraz fazlası olduğundan özellikle basittir. Bir ikili değerler dizisindeki sıfır olmayan bitlerin sayısını sayan Hamming ağırlığı veya popülasyon sayımı işlemi, tekli sayılardan ikili sayılara dönüşüm olarak da yorumlanabilir. Bununla birlikte, çarpma daha zahmetlidir ve sıklıkla Turing makinelerinin tasarımı için bir test senaryosu olarak kullanılmıştır.

Karmaşıklık 
Standart konumsal sayı sistemleri ile karşılaştırıldığında, tekli sistem elverişsizdir ve bu nedenle pratikte büyük hesaplamalar için kullanılmaz. Teorik bilgisayar bilimindeki bazı karar problemi tanımlarında (örneğin, bazı P-Tam problemleri) ortaya çıkar ve bir problemin çalışma süresini veya alan gereksinimlerini "yapay olarak" azaltmak için kullanılır. Örneğin, tamsayı çarpanlara ayırma probleminin, girdileri ikili olarak verilmişse, çalışma süresi olarak girdi uzunluğunun bir polinom fonksiyonundan fazlasını gerektirdiğinden şüphelenilmektedir, ancak giriş tekli olarak sunuluyorsa yalnızca doğrusal çalışma süresine ihtiyaç duyar.  Ancak, bu potansiyel olarak yanıltıcıdır. Tekli giriş kullanmak herhangi bir sayı için daha hızlı değildir; ayrım, bir ikili (veya daha büyük tabanda) girdinin, sayının 2 veya daha büyük tabanda logaritması ile orantılı iken, tekli girdinin sayının kendisiyle orantılı olmasıdır. Bu nedenle, tek terimli çalışma zamanı ve alan gereksinimi, girdi boyutunun fonksiyonu olarak daha iyi görünürken, daha verimli bir çözümü temsil etmemektedir.

Hesaplamalı karmaşıklık teorisinde, tekli numaralandırma, güçlü NP-tam problemlerini NP-tam olan fakat güçlü bir şekilde NP-tam olmayan problemlerden ayırmak için kullanılır. Girdinin bazı güçlü şekilde NP-tam olan sayısal parametreleri içerdiği bir problem, girdinin boyutu, parametrelerin tekli olarak gösterilmesiyle yapay olarak daha büyük hale getirildiğinde bile NP-tam olarak kalırsa, güçlü bir şekilde NP-tam değildir. Böyle bir problem için, tüm parametre değerlerinin en çok polinomik olarak büyük olduğu zor durumlar vardır.

Uygulamalar 
Tekli numaralandırma, Golomb kodlaması gibi bazı veri sıkıştırma algoritmalarının bir parçası olarak kullanılır. Ayrıca, matematiksel mantık içinde aritmetiği biçimlendirmek için Peano aksiyomlarının temelini oluşturur. Lambda hesabı içindeki sayıları temsil etmek için Church kodlaması adı verilen bir tekli gösterim biçimi kullanılır.

Kaynakça 

Formal dilleri
Kodlama teorisi
Temel matematik
Bir
Sayı sistemleri