可能的保留输出的代码操作集
这是一个理论问题，因此这里的许多细节在实践中甚至在理论上都是不可计算的。
假设我有一个要压缩的字符串 s。结果应该是一个输出 s 的自解压二进制文件（可以是 x86 asm，但也可以是其他假设的图灵完备低级语言）。
现在，我们可以轻松地迭代所有可能的此类二进制文件/程序，并按大小排序。令B_s为输出s的这些二进制文件的子列表（当然B_s是不可计算的）。
由于每组正整数都必须有一个最小值，因此 B_s 中必定有一个最小的程序 b_min_s，
从 s 中，我还可以构造一个规范的程序 b_cano_s 只以简单的方式输出 s 。即，如果我们考虑 ELF 带有数据段，我们甚至会有#b_cano_s ~ #s。
二进制文件上是否存在一组可能的操作：
1 .将保留输出。
2a.给定b_cano_s，我们可以通过A的操作以某种方式到达b_min_s。
（2b.给定b_cano_s，我们可以得到B_s中的所有程序。）
对于所有可能的字符串s。
条件1+2a弱于条件1+2b。也许，如果有这样一个集合A，我们就会自动拥有两者。 （是这样吗？）
这样的集合A存在吗？我正在考虑一些明显的操作，例如搜索一些重复的字符串并缩短它。或者其他一些常见的压缩方法。然而，这可能不足以达到所有程序B_s，而且我的意图是出于同样的原因也不一定达到b_min_s。
如果存在，我们能否表达它，即它是否可计算？
This is a theoretical question, so expect that many details here are not computable in practice or even in theory.
Let's say I have a string s that I want to compress. The result should be a self-extracting binary (can be x86 asm but can also be some other hypothetical Turing-complete low level language) which outputs s.
Now, we can easily iterate through all possible such binaries/programs, ordered by size. Let B_s be the sub-list of these binaries who output s (of course B_s is uncomputable).
As every set of positive integers must have a minimum, there must be a smallest program b_min_s in B_s
From s, I can also construct a canonical program b_cano_s which just outputs s in a trivial way. I.e. the size of b_cano_s will be in O(#s) -- if we think of ELF with data segments, we will even have #b_cano_s ~ #s.
Is there a set A of possible operations on the binaries which:
1 . Will preserve the output.
2a . Given b_cano_s, we can arrive somehow by operations from A at b_min_s.
(2b . Given b_cano_s, we can arrive at all programs in B_s.)
for all possible strings s.
The conditions 1+2a are weaker than the conditions 1+2b. Maybe, if there is such a set A, we will automatically have both, though. (Is that so?)
Does such a set A exists? I was thinking about some obvious operations, like searching for some repeated strings and shorten this. Or some of the other common compression methods. However, that probably is not enough to arrive at all programs B_s and my intention says also not necessarily at b_min_s for the same reason.
If it exists, can we express it, i.e. is it computable?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
您应该链接您的相关之前的问题。
2a.如前所述，您无法确定
b_min_s，因为这会导致悖论。因此，我认为你无法证明 A 中的操作足以减少到它。2b.您可以暴力破解
B_s，但这是一个无限集，并且该过程是非终止的。但是，对于B_s中的每个程序，您可以计算从b_cano_s到B_s的操作。然而，这并不意味着这些可能的操作将是有意义的。似乎“删除此范围内的字符”、“在此位置插入字符”等操作符合条件。You should link your related previous questions.
2a. As noted, you can not determine
b_min_s, because that results in a paradox. As a result, I don't think you can prove the operations in A are sufficient to reduce to it.2b. You can brute force
B_s, but this is an infinite set, and the procedure is non-terminating. However, for each program inB_s, you can calculate a manipulation fromb_cano_stoB_s. However, that does not imply these possible operations will be meaningful. It seems operations like "delete characters in this range", "insert character at this position" qualify.