Tekli sayı sistemi
| Rakam sistemleri |
|---|
 |
| Hint-Arap rakam sistemi |
| Doğu Asya |
|
| Alfabetik |
| Eski |
|
| Tabana göre sayı sistemleri |
| Non-standard positional numeral systems |
|
| Sayısal sistemler listesi |
Tekli sayı sistemi, doğal sayıları temsil eden en basit sayı sistemidir:[1] bir N sayısını temsil etmek için, 1'i temsil eden bir simge N kez tekrarlanır.[2]
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.[3]
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.[4] (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.[5][6]
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.[7] 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.[8] Bununla birlikte, çarpma daha zahmetlidir ve sıklıkla Turing makinelerinin tasarımı için bir test senaryosu olarak kullanılmıştır.[9][10][11]
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.[12][13] 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.[14]
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.[15]
Uygulamalar
Tekli numaralandırma, Golomb kodlaması gibi bazı veri sıkıştırma algoritmalarının bir parçası olarak kullanılır.[16] Ayrıca, matematiksel mantık içinde aritmetiği biçimlendirmek için Peano aksiyomlarının temelini oluşturur.[17] Lambda hesabı içindeki sayıları temsil etmek için Church kodlaması adı verilen bir tekli gösterim biçimi kullanılır.[18]
Kaynakça
- ^ One to Nine: The Inner Life of Numbers, Anchor Canada, 2009, s. 14, ISBN 9780385672665, 29 Haziran 2016 tarihinde kaynağından arşivlendi, erişim tarihi: 28 Aralık 2020
- ^ Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science, Computer Science and Scientific Computing, Academic Press, 1994, s. 117, ISBN 9780122063824, 24 Nisan 2016 tarihinde kaynağından arşivlendi, erişim tarihi: 28 Aralık 2020.
- ^ Programming Structures: Machines and Programs, Programming Structures, 1, Prentice Hall, 1990, s. 33, ISBN 9780724809400.
- ^ The Evolution of Modern Numerals from Ancient Tally Marks, 16 (8–9), 1909, ss. 125-33, doi:10.2307/2970818.
- ^ Chinese Tally Mark, 35 (3), 1981, s. 174, doi:10.2307/2683999
- ^ "Proposal to Encode Five Ideographic Tally Marks", Unicode Consortium (PDF), 27 Ocak 2016, Proposal L2/16-046, 30 Eylül 2020 tarihinde kaynağından arşivlendi (PDF), erişim tarihi: 28 Aralık 2020
- ^ "On feasible numbers", Logic and computational complexity (Indianapolis, IN, 1994), Lecture Notes in Comput. Sci., 960, Springer, Berlin, 1995, ss. 30-51, doi:10.1007/3-540-60178-3_78, ISBN 978-3-540-60178-4. See in particular p. 48.
- ^ Blaxell, David (1978), "Record linkage by bit pattern matching", Computer Science and Statistics--Tenth Annual Symposium on the Interface, NBS Special Publication, 503, U.S. Department of Commerce / National Bureau of Standards, ss. 146-156, 24 Şubat 2017 tarihinde kaynağından arşivlendi, erişim tarihi: 28 Aralık 2020.
- ^ Introduction to Automata Theory, Languages, and Computation, Addison Wesley, 1979, ISBN 978-0-201-02988-8.
- ^ The New Turing Omnibus: Sixty-Six Excursions in Computer Science, Computer Science Press, 1989, s. 209, ISBN 9780805071665, 4 Mayıs 2016 tarihinde kaynağından arşivlendi, erişim tarihi: 28 Aralık 2020.
- ^ "5.3 Larger Example TM: Unary Multiplication", Turing Machine Universality of the Game of Life, Emergence, Complexity and Computation, 18, Springer, 2015, ss. 83-86, ISBN 9783319198422, 10 Haziran 2016 tarihinde kaynağından arşivlendi, erişim tarihi: 28 Aralık 2020.
- ^ "The computational model —and why it doesn't matter" (PDF), Computational Complexity: A Modern Approach, January 2007 draft, Cambridge University Press, 2007, erişim tarihi: 10 Mayıs 2017.
- ^ CPSC 468/568 HW1 Solution Set (PDF), Computer Science Department, Yale University, Sonbahar 2012, erişim tarihi: 21 Ekim 2014[].
- ^ The Nature of Computation, Oxford University Press, 2011, s. 29, ISBN 9780199233212, 22 Mayıs 2016 tarihinde kaynağından arşivlendi, erişim tarihi: 28 Aralık 2020.
- ^ 'Strong' NP-completeness results: Motivation, examples, and implications, 25 (3), 1978, ss. 499-508, doi:10.1145/322077.322090.
- ^ Run-length encodings, IT-12 (3), 1966, ss. 399-401, doi:10.1109/TIT.1966.1053907, 20 Şubat 2020 tarihinde kaynağından arşivlendi, erişim tarihi: 28 Aralık 2020.
- ^ "Changing data structures in type theory: a study of natural numbers", Types for proofs and programs (Durham, 2000), Lecture Notes in Comput. Sci., 2277, Springer, Berlin, 2002, ss. 181-196, doi:10.1007/3-540-45842-5_12, ISBN 978-3-540-43287-6.
- ^ "Programming in the λ-calculus: from Church to Scott and back", The Beauty of Functional Code: Essays Dedicated to Rinus Plasmeijer on the Occasion of His 61st Birthday, Lecture Notes in Computer Science, 8106, Springer-Verlag, 2013, ss. 168-180, doi:10.1007/978-3-642-40355-2_12, ISBN 978-3-642-40354-5.
