Wang瓷砖（多米诺骨牌）是由Hao Wang于1961年发明的，用于解决数学问题，但在游戏中广泛用于创建瓷砖图形。 多亏了他们，无论是在2D纹理中还是在带有贴图的3D模型中，结果看起来都不是重复的。
Van的tile似乎也可以执行Turing机器，因此它们是Turing完整的，这意味着它们可以执行任何程序。
这是一个令人惊奇且难以理解的声明，因此在这篇文章中，我将对此问题进行一些调查。
简要介绍Van Tiles
范式图块是矩形图块，其中每个面只能对应于其他特定面，但是对于任何特定面，有几种可能的图块可以对应于该面。 通过匹配面，我的意思是它们可以无缝连接，而不会在砖之间创建任何视觉假象或接缝痕迹。
此属性对图形很有用，因为它允许您创建无缝的瓦片图形，但是只要所有面彼此兼容，瓦片的位置配置就可以完全随机化。 结果是平铺图形，这根本不像重复的平铺图形，因为视觉图案变得比传统平铺图形不那么引人注目。
图形示例，更多详细信息以及与Shadertoy的链接可以在这里找到：
Wang Tiling 。
这是我创建的示例。 我的图形是“艺术程序员”，但我希望这个想法很明确。 该图形由16个图块组成，每个面都有两种不同类型的面。
关于图灵机的简要介绍
图灵机由Alan Turing于1936年发明，是一台通用计算机，事实证明该机可以执行任何算法。
图灵机由几个主要组件组成：存储带，读/写头和状态机。
存储带的长度是无限的，也就是说，存储容量是无限的，并且在开始时仅用零初始化。
读/写头从磁带的某个位置开始，可以读取/写入值，也可以沿着磁带左右移动。
状态机控制读/写头。
状态机知道它所处的状态，并具有从磁带读取值时在每种状态下要做什么的规则。
例如，在状态A中，如果从磁带上读取了0，则规则可以是将1写入磁带的当前位置，向右移动读/写头，或转到状态B。状态B可以具有完全不同的逻辑，并且可以执行转换返回状态A，或停留在状态B，或移至完全不同的状态。
使用状态之间的这种简单转换逻辑，可以执行任何计算机算法。
图灵机还可能具有“暂停状态”，这意味着程序已完成执行并且已计算出响应。
寻找一些程序。 很容易看出来。 随着时间的流逝，它们将结束或陷入无限循环，并且永不停止。 有些程序位于它们之间，它们很复杂，要确定它们是否会停止并不容易。 图灵证明，没有通用的解决方案来确定图灵机是否将停止（这是一个计算机程序），这称为
停止问题 。 通常，找出程序是否停止的唯一方法是等待。 也就是说，实际上，在一般情况下，此问题的答案是“是”或“尚未”，但是，对于许多特定程序，您可以看到它们在启动后会随着时间的推移而终止。
王瓦计算
事实证明，Wang tile可以模拟图灵机，也就是说，它们是图灵完备的，这意味着它们可以执行任何计算机算法。
为了实现这一点，我们需要一列Van tile，以指示图灵机在特定时间点（从最左列的时间0开始）的状态。 我们将把带有所有面规则的图块放在右边的列中，然后在它的右边创建一个列，依此类推，直到程序终止（或者如果它没有结束，我们将永远这样做）。 如果选择正确的一组图块，那么在排列图块的过程中检查是否符合面的规则就足以完成图灵机。
让我们看一个具有以下状态机逻辑规则的简单示例：
- 当机器处于状态A时，在读取0的情况下，我们写入1，将读/写头向下移，进入状态B。
- 当机器处于状态A时，在读取1的情况下，程序停止（切换到最终状态）。
- 当机器处于状态B时，在读取0的情况下，我们写入1，将读写头向上移动并进入状态A。
- 当机器处于状态B时，在读取1的情况下，程序停止（进入最终状态）
磁带机
首先，我们需要将磁带永久保存。 为此，我们需要以下两个磁贴：
为了测试他们的工作，我们可以准备一部分带有一些值的磁带（创建一列Van Tile，并确保位于初始列旁边的唯一合适的Van Tile是在时间上向前传递值0和1而不改变的瓦片）他们。
在下图中，我们在最左侧的列（时间0）中使用值0101初始化磁带。 仅具有具有兼容面的图块，我们看到内存中的值将永久存储。 我们已经实现了内存驱动器！
我们将开始演示将内存初始化为0的示例，并且上图仅显示了内存的持久性。
读写头状态机
图灵机的读/写头是面部信息的一部分。 因此，除了存储0或1的面之外，如果其中包含读/写头，那么它还存储状态机的状态。
在我们的示例中，使用了两种状态（不包括最终状态）：A和B。如果读取了1，则在任何状态（A或B）中，程序都会结束。
要处理此问题，我们需要以下图块：
现在我们有了转换到最终状态的规则（规则2和4），我们需要了解如何实现控制从一种状态切换到另一种状态的规则（规则1和3）。
移动读/写头
规则1指出，如果我们处于状态A且读为0，则必须写1，将读/写头向下移，然后进入状态B。
我们需要此图块在状态A下读取0，将1写入输出，并命令下面的图块进入状态B。
当前图块下方的图块可以具有0或1的值； 在不知道特定值的情况下，我们必须保存它，但是接受读/写头并处于状态B。为此，我们需要两个磁贴-一个在此位置上的磁带上为0，另一个在磁带上为1。
规则3指出，如果我们处于状态B且读为0，则必须写1，将读写头抬高并进入状态A。
为此，我们需要一个类似于规则1的构造，但是我们不是向下移动而是向上移动。 以下三个图块将提供所需的结果：
初始列磁贴
我们将感知模拟区域的边界，就像它们具有“ x”面一样。
这意味着要创建初始列（时间为0的图灵机），我们需要两个特殊的图块。 一个磁贴需要在磁带上存储值0，这将初始化磁带；另一个磁贴需要在状态A（即我们的初始状态）下存储读/写头的位置。
这两个磁贴为：
准备一套瓷砖
这是我们将使用的完整的12个图块集：
全面模拟
这是图灵机在时间0时的原始设计。请注意，这是可能的初始状态之一，但这是我们选择的状态。 我们没有机会选择读/写头开始的位置以及它的存在。 如果仅遵循面孔规则，那么我们可以得到4个或0个读写头，或它们之间的任何数量。
从这里开始，创建第二列，我们从顶部开始向下移动，选择一个与其所接触的面的限制相匹配的图块。 在此第一步中，磁头读取0，写入1，向下移动并进入状态B。
这是第二步，其中磁头读0，写1，然后向上移动并进入状态A。
这是磁头读取1并进入最终状态的最后一步，表明程序已完成。
该程序结束并给了我们0110或6的输出值。这些输出值不是特别重要，但是其他程序可以产生重要的输出。 例如，我们可以强制图灵机将两个数字相加，并且输出将是这两个数字的总和。
重要细节
在这里，我们必须提到一个我们上面没有考虑的重要细节，而范式瓷砖上的图灵机的大多数说明都没有提到这一细节。
将第二块图块放置为时间2时，对面的唯一限制是该图块的顶部必须为x，左侧必须为1。 实际上，由于这个原因，情况变得模棱两可，因为尚不清楚应选择下面显示的两个图块中的哪个。
那我们该如何选择合适的呢？
答案是我们只是做一个假设，然后选择其中一个。 如果在这种情况下选择了错误的图块，那么当我们移至下一个图块时，我们将寻找顶部为x且左侧为B0的图块。 这样的图块不存在，因此我们不能放置图块。 发生这种情况时，我们需要返回到最后一个磁贴并尝试其他选项之一。
也就是说，不幸的是，当使用Wang贴图来模拟Turing机器时，确实存在一个反复试验的过程，但是至少它是相当可管理的。 它确实使像素着色器（或其他具有高并行度的设备）的计算复杂化了一点，但是成本却不高。
结论和链接
下面的一些链接讨论了Wang瓷砖和Turing机，但是这些讨论似乎并不严格遵守Turing机。 例如，您可能会注意到，在某些示例中，允许数据返回“及时返回”-当程序终止时，答案在图灵机的时间0处在磁带上，尽管事实上该数据在时间0处不存在。这表明Wang tile可以自己进行计算，而不仅是模拟图灵机，而且我不知道到底该技术叫什么。
另外，如果您想知道什么对使用Wang块进行计算有用，那么我个人无法想象它们实际应用的情况。 但是，科学家似乎已经发现，DNA的作用与Van tile几乎相同，因为它们仅在兼容的表面之间建立连接。 由于这个原因，现在正在基于使用Wang块的计算过程来研究基于DNA的计算。 非常有趣的话题！
这是在WebGL像素着色器的Shadertoy中使用Wang切片计算素数的实现：
Shadertoy：WangTiles：PrimeGenerator以下是有关图灵车和停车问题的更多精彩视频：
图灵机解释-Computerphile图灵与停止问题-Computerphile还有更多链接：
瓷砖计算维基百科：范瓷砖王瓷砖和图灵机王瓷砖-1以下是一些科学文章：
瓷砖计算平铺的可计算性