主题
Search

自动集

一个 k-自动集是一个整数集合，其基数-k 表示形式构成一种正则语言，即一种可由有限自动机或状态机接受的语言。如果基数 a 和 b 不兼容（没有共同的幂），并且如果一个 a-自动集 S_a 和一个 b-自动集 S_b 在整数上都具有密度 0，那么人们认为 S_a intersection S_b 是有限的。然而，这个问题尚未解决。

一些自动集，例如由数字组成的 2-自动集，这些数字的二进制表示最多包含两个 1：1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 16, 17, 18, ... (OEIS A048645) 具有简单的算术表达式。然而，对于一般的 k-自动集情况并非如此。

另请参阅

图灵机

使用 探索

参考文献

Cobham, A. "On the Base-Dependence of Sets of Numbers Recognizable by Finite Automata." Math. Systems Th. 3, 186-192, 1969.Cobham, A. "Uniform Tag Sequences." Math. Systems Th. 6, 164-192, 1972.Sloane, N. J. A. Sequence A048645 in "The On-Line Encyclopedia of Integer Sequences."

在 中被引用

自动集

引用为

Weisstein, Eric W. "Automatic Set." 来自 —— Wolfram 网络资源。 https://mathworld.net.cn/AutomaticSet.html

主题分类