Persamaan Himpunan Bilangan Asli Hanya Terhadap Penjumlahan

Abstract

Systems of equations of the form X = Y + Z dan XC, in which the unknowns are sets of integers, "+" denotes pairwise sum of sets S+T= {m + n|m € S, ne T}, and C is an ultimately periodic constant. When restricted to sets of natural numbers, such equations can be equally seen as language equations over a one-letter alphabet with concatenation and regular constants, and it is shown that such systems are computationally universal, in the sense that for every recursive set SCN there exists a system with a unique solution containing T with S = {n/16n+13 € T). For systems over sets of all integers, both positive and negative, there is a similar construction of a system with a unique solution S = {n|16n € T} representing any hyper-arithmetical set SC N.