Tekli sayı sistemi doğal sayıları temsil eden en basit sayı sistemidir bir N sayısını temsil etmek için 1 i tem

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ı , 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 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 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ı 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 adı verilen bir tekli gösterim biçimi kullanılır.

Kaynakça

^ One to Nine: The Inner Life of Numbers, Anchor Canada, 2009, s. 14, ISBN , 29 Haziran 2016 tarihinde kaynağından , 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 , 24 Nisan 2016 tarihinde kaynağından , erişim tarihi: 28 Aralık 2020 .
^ Programming Structures: Machines and Programs, Programming Structures, 1, Prentice Hall, 1990, s. 33, ISBN .
^ 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 (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 . 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 , erişim tarihi: 28 Aralık 2020 .
^ Introduction to Automata Theory, Languages, and Computation, Addison Wesley, 1979, ISBN .
^ The New Turing Omnibus: Sixty-Six Excursions in Computer Science, Computer Science Press, 1989, s. 209, ISBN , 4 Mayıs 2016 tarihinde kaynağından , 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 , 10 Haziran 2016 tarihinde kaynağından , 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 , 22 Mayıs 2016 tarihinde kaynağından , 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 , 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 .
^ "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 .

[1] One to Nine: The Inner Life of Numbers, Anchor Canada, 2009, s. 14, ISBN , 29 Haziran 2016 tarihinde kaynağından , erişim tarihi: 28 Aralık 2020

[2] Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science, Computer Science and Scientific Computing, Academic Press, 1994, s. 117, ISBN , 24 Nisan 2016 tarihinde kaynağından , erişim tarihi: 28 Aralık 2020 .

[3] Programming Structures: Machines and Programs, Programming Structures, 1, Prentice Hall, 1990, s. 33, ISBN .

[4] The Evolution of Modern Numerals from Ancient Tally Marks, 16 (8–9), 1909, ss. 125-33, doi:10.2307/2970818 .

[5] Chinese Tally Mark, 35 (3), 1981, s. 174, doi:10.2307/2683999

[Lunde_2016-2-6] "Proposal to Encode Five Ideographic Tally Marks", Unicode Consortium (PDF), 27 Ocak 2016, Proposal L2/16-046, 30 Eylül 2020 tarihinde kaynağından (PDF), erişim tarihi: 28 Aralık 2020

[7] "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 . See in particular p. 48.

[blaxell-8] 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 , erişim tarihi: 28 Aralık 2020 .

[9] Introduction to Automata Theory, Languages, and Computation, Addison Wesley, 1979, ISBN .

[10] The New Turing Omnibus: Sixty-Six Excursions in Computer Science, Computer Science Press, 1989, s. 209, ISBN , 4 Mayıs 2016 tarihinde kaynağından , erişim tarihi: 28 Aralık 2020 .

[11] "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 , 10 Haziran 2016 tarihinde kaynağından , erişim tarihi: 28 Aralık 2020 .

[12] "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 .

[13] CPSC 468/568 HW1 Solution Set (PDF), Computer Science Department, Yale University, Sonbahar 2012, erişim tarihi: 21 Ekim 2014 ^[].

[14] The Nature of Computation, Oxford University Press, 2011, s. 29, ISBN , 22 Mayıs 2016 tarihinde kaynağından , erişim tarihi: 28 Aralık 2020 .

[15] 'Strong' NP-completeness results: Motivation, examples, and implications, 25 (3), 1978, ss. 499-508, doi:10.1145/322077.322090 .

[16] Run-length encodings, IT-12 (3), 1966, ss. 399-401, doi:10.1109/TIT.1966.1053907, 20 Şubat 2020 tarihinde kaynağından , erişim tarihi: 28 Aralık 2020 .

[17] "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 .

[18] "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 .