我的猫图灵完备吗? - belaycpp

21-11-30 banq

本周我将触及一个更轻松的主题,但仍然非常重要:我的猫图灵完备吗?

Peluche(法语中的“毛绒”的意思)是一只光滑的猫,不知何故住在我家。

她将是我们今天的测试对象。

 

Peluche 图灵完备吗?

 

什么是图灵完备

图灵完备性的概念是,如果设备可以模拟图灵机,那么它就可以执行任何类型的计算1

这意味着任何实现以下八条指令的机器都是一台计算机(因此可以执行任何类型的计算):

  • .与,: 输入和输出一个值
  • +与-:增加和减少存储单元包含的值。
  • >与<:向左或向右移动当前存储磁带。
  • [ and ]:执行循环。

所以,如果 Peluche 能够执行这八个指令,我们可以考虑她的图灵完备。

 

图灵完备性的证明

  • 输入输出

首先,如果我能得到反应,我会尝试戳 Peluche。她看了我一眼,然后才转过身。所以它是这样的:我戳了她一下,我得到了一个反应。所以她可以处理输入并给出输出。

输入/输出确认!

  • 增减内存值

前几天,我下班回来:瓷砖上到处都是猫粮……

但后来我仔细看了一下,意识到可以对瓷砖块进行编号,对我来说,这看起来很像记忆带!由于她可以将猫尿从猫粮盆中洒在瓷砖上,然后直接从瓷砖上吃掉它们,因此她可以增加和减少给定存储单元中包含的值。增加/减少确认!

  • 向左或向右移动当前内存单元

还有一次,我在洗碗时不小心洒了一些水在 Peluche 身上。她开始在厨房里到处乱跑,弄得一团糟。

在弄得一团糟时,她移动了她的碗。

由于碗的移动,她又会将猫粮洒在另一块瓷砖上。这算作移动内存头以编辑另一个内存单元。

已确认存储磁带的移位!

  • 执行循环

所以,在这个烂摊子之后,我(显然)不得不清理。

不到五分钟后,瓷砖上又撒有猫粮了。

是的......她绝对可以执行循环......

循环确认!

 

我们刚刚证明了 Peluche 确实是图灵完备的。那么现在,我们如何使用她来执行高性能计算?

现在我已经证明 Peluche 是图灵完备的,我可以对她做任何事情!

因此,我试图给她简单的代码来执行:

..........

执行结果是我们知道的:她什么都不做。

虽然它们可以,但也许猫根本不是为了执行代码而设计的?

 

这是一个幽默笑话。

1
猜你喜欢