在计算机科学中，有没有一个词来表示所有数据表示都是相等的这一事实？

Question

对于编程语言，我们有图灵完备性的概念，它表达了这样一个事实，即只要我们忽略存储介质的容量，所有计算机和所有语言在表示任何算法的能力方面都是平等的。有没有类似的词来表示数据编码/表示？

例如，任何数字都可以用一元、二进制、三元形式表示。只要所有的数据结构在任何给定的2个结构A和B之间具有相同的“数据容量”，就存在函数：

to :: A → B
from :: B → A

from ∘ to == id在哪里。

这显然适用于存在于计算机中的任何(上下文无关)数据结构，因为它们从字面上看都只是位串。但是这个词是什么呢？

Answer 1

从技术上讲，我认为你指的是图灵等价，而不是图灵完备性，图灵完备性是相似但不相同的东西。至于你的问题:我不认为有一个通用的术语来描述它，除了可能说两个编码是等价的。如果你有一种特殊的编码，你想用它作为标准，比如十进制编码数字，如果你说二进制是编码数字的十进制等价系统，你会理解的。

当然，如果您的意思是两个系统不仅在语义上是等价的(它们可以对相同的东西进行编码)，而且在语法上也是等价的(它们的编码基本上是以相同的方式工作的)，您可以使用类似于同构的术语(意思是一种编码中的每个字符串映射到另一种编码中的一个字符串，反之亦然)。