Compaction of Church Numerals
In this study, we address the problem of compaction of Church numerals. Church numerals are unary representations of natural numbers on the scheme of lambda terms. We propose a novel decomposition scheme from a given natural number into an arithmetic expression using tetration, which enables us to o...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2019-08-01
|
| Series: | Algorithms |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1999-4893/12/8/159 |
| _version_ | 1811287910005080064 |
|---|---|
| author | Isamu Furuya Takuya Kida |
| author_facet | Isamu Furuya Takuya Kida |
| author_sort | Isamu Furuya |
| collection | DOAJ |
| description | In this study, we address the problem of compaction of Church numerals. Church numerals are unary representations of natural numbers on the scheme of lambda terms. We propose a novel decomposition scheme from a given natural number into an arithmetic expression using tetration, which enables us to obtain a compact representation of lambda terms that leads to the Church numeral of the natural number. For natural number <i>n</i>, we prove that the size of the lambda term obtained by the proposed method is <inline-formula> <math display="inline"> <semantics> <mrow> <mi mathvariant="script">O</mi> <mo stretchy="false">(</mo> <msup> <mrow> <mo stretchy="false">(</mo> <msub> <mi>slog</mi> <mn>2</mn> </msub> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> <mrow> <mo stretchy="false">(</mo> <mo form="prefix">log</mo> <mi>n</mi> <mo>/</mo> <mo form="prefix">log</mo> <mrow> <mo form="prefix">log</mo> <mi>n</mi> </mrow> <mo stretchy="false">)</mo> </mrow> </msup> <mo stretchy="false">)</mo> </mrow> </semantics> </math> </inline-formula>. Moreover, we experimentally confirmed that the proposed method outperforms binary representation of Church numerals on average, when <i>n</i> is less than approximately 10,000. |
| first_indexed | 2024-04-13T03:26:45Z |
| format | Article |
| id | doaj.art-e17b6ba63779470d814f00e1316988bc |
| institution | Directory Open Access Journal |
| issn | 1999-4893 |
| language | English |
| last_indexed | 2024-04-13T03:26:45Z |
| publishDate | 2019-08-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Algorithms |
| spelling | doaj.art-e17b6ba63779470d814f00e1316988bc2022-12-22T03:04:38ZengMDPI AGAlgorithms1999-48932019-08-0112815910.3390/a12080159a12080159Compaction of Church NumeralsIsamu Furuya0Takuya Kida1Graduate School/Faculty of Information Science and Technology, Hokkaido University, Kita 14 Nishi 9, Sapporo 060-0814, JapanGraduate School/Faculty of Information Science and Technology, Hokkaido University, Kita 14 Nishi 9, Sapporo 060-0814, JapanIn this study, we address the problem of compaction of Church numerals. Church numerals are unary representations of natural numbers on the scheme of lambda terms. We propose a novel decomposition scheme from a given natural number into an arithmetic expression using tetration, which enables us to obtain a compact representation of lambda terms that leads to the Church numeral of the natural number. For natural number <i>n</i>, we prove that the size of the lambda term obtained by the proposed method is <inline-formula> <math display="inline"> <semantics> <mrow> <mi mathvariant="script">O</mi> <mo stretchy="false">(</mo> <msup> <mrow> <mo stretchy="false">(</mo> <msub> <mi>slog</mi> <mn>2</mn> </msub> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> <mrow> <mo stretchy="false">(</mo> <mo form="prefix">log</mo> <mi>n</mi> <mo>/</mo> <mo form="prefix">log</mo> <mrow> <mo form="prefix">log</mo> <mi>n</mi> </mrow> <mo stretchy="false">)</mo> </mrow> </msup> <mo stretchy="false">)</mo> </mrow> </semantics> </math> </inline-formula>. Moreover, we experimentally confirmed that the proposed method outperforms binary representation of Church numerals on average, when <i>n</i> is less than approximately 10,000.https://www.mdpi.com/1999-4893/12/8/159loss-less compressionlambda termhigher-order compression |
| spellingShingle | Isamu Furuya Takuya Kida Compaction of Church Numerals Algorithms loss-less compression lambda term higher-order compression |
| title | Compaction of Church Numerals |
| title_full | Compaction of Church Numerals |
| title_fullStr | Compaction of Church Numerals |
| title_full_unstemmed | Compaction of Church Numerals |
| title_short | Compaction of Church Numerals |
| title_sort | compaction of church numerals |
| topic | loss-less compression lambda term higher-order compression |
| url | https://www.mdpi.com/1999-4893/12/8/159 |
| work_keys_str_mv | AT isamufuruya compactionofchurchnumerals AT takuyakida compactionofchurchnumerals |