成为VIP会员查看完整内容
VIP会员码认证
首页
主题
发现
会员
服务
注册
·
登录
0
猫=图灵机?4项测试证明,「猫猫计算机」可执行任意计算
2021 年 12 月 8 日
新智元
新智元报道
编辑:David 小咸鱼
【新智元导读】
近日,一位法国开发者Chloé Lourseyre在她的个人博客上提出了「猫猫计算机」的概念。由此,她提出了一个天马行空的想法:猫是不是「图灵完备」的?它是「图灵机」吗?
软萌可爱的猫咪,总会唤起我们想要「撸猫」或者「吸猫」的冲动。
和猫咪待在一块,还真有种治愈的感觉。
而且,按照一位法国开发者Chloé Lourseyre的说法,猫咪甚至可以当计算机用!
近日,在她的个人博客上讨论了一个很重要的话题:猫是不是「图灵完备」的?它是「图灵机」吗?
测试对象就是这只小猫Peluche
Peluche是一只毛茸茸的小猫,就住在Chloé Lourseyre家里。它就是今天的测试对象。
什么是图灵完备?
图灵完备性的概念是,如果某台设备可以模拟图灵机,那么它就可以执行任何类型的计算。
也就是说,任何能够通过以下4项测试的机器都是一台计算机(因此可以执行任何类型的计算)。
这
4项测试
是:
. 和 , —— 输入和输出一个值。
+ 和 - —— 增加和减少当前存储单元中包含的值。(图灵机有一个「存储带」,上面有「存储单元」。机器总是指向一个存储单元,也就是上面提到的「当前」存储单元。)
> 和 < —— 向左或向右移动当前存储单元。
[ 和 ] —— 执行循环。
所以,如果 Peluche 能够通过这
4项测试
,就可以认为它是「图灵完备」的。
图灵完备性的证明
输入输出
首先,为了验证能不能得到反馈,Chloé Lourseyre用手戳了戳 Peluche。
它看了Chloé Lourseyre一眼,然后才转过身。
所以是这样的:Chloé Lourseyre戳了它一下,然后得到了一个反应。结论很明确,Peluche可以处理输入,并给出输出。
输入、输出已确认!
增减内存值
前几天,Chloé Lourseyre下班回来,发现厨房变成了这样:
到处都是猫粮……
但后来Chloé Lourseyre仔细观察了一下,发现可以把撒上猫粮的地板按位置进行编号,就像下面这样:
在Chloé Lourseyre看来,这看起来很像内存带!Peluche可以将猫粮洒在地砖上,然后直接在地砖上吃掉它们,因此,Peluche可以增加和减少给定存储单元中包含的值。
增减内存值,已确认!
左右移动当前内存单元
还有一次,Chloé Lourseyre在洗碗时不小心把一些水洒在了 Peluche 身上。它开始在厨房里到处乱跑,弄得一团糟。
但是如果仔细观察(在红色箭头的尖端),不难注意到,Peluche一边乱跑,一边把自己装食物的碗移动了位置。
也就是说,Peluche将它的食物洒到另一块瓷砖上。这相当于移动指向当前内存的指针,编辑另一个内存单元。
移动内存单元,已确认!
执行循环
在厨房被Peluche搞的一团乱之后,很明显,Chloé Lourseyre不得不清理打扫。
然后不到五分钟后,Chloé Lourseyre回到厨房,又变成这样了:
所以,Peluche绝对可以执行循环......
循环已确认!
到这里为止,Chloé Lourseyre已经证明了Peluche确实是「图灵完备」的。那么下一个问题是,如何使用Peluche来执行高性能计算任务?
如何执行?首先要有代码,Chloé Lourseyre编了一段简单的代码,就像下面这样:(这个代码示例是一种奇特的新语言,名为「braincat」)
结果:Peluche什么都不做!
所以最后,Chloé Lourseyre不禁想,虽然猫是「图灵完备」的,但可能不是为了执行代码而设计的?
关于「猫猫计算机」
上面的「猫猫计算机」当然都是说笑话。
根据Chloé Lourseyre的经验,当有人发现一种语言的新特征时,就开始到处使用。
「猫猫计算机」似乎是一个新手会犯的错误,但即使是最有经验的开发人员,有时也会犯新手错误,承认这一点没什么难为情的。
实际上,在面对编程语言的全新版本中的新功能时,积累经验的最好办法,就是把每个功能错误地使用一次,以避免今后的误用。
在使用某项功能之前,一定要先问问自己,这样做实际上是否有必要,否则你也可能犯下像「猫猫计算机」这样的错误。
另外,猫猫计算机很费猫,所以不要这样做。
(此文的写作过程中,没有猫猫受到伤害,但有一只猫被轻轻地戳过几下。)
参考资料:
https://belaycpp.com/2021/11/24/is-my-cat-turing-complete/
https://en.wikipedia.org/wiki/Turing_completeness
登录查看更多
点赞并收藏
0
暂时没有读者
0
权益说明
本文档仅做收录索引使用,若发现您的权益受到侵害,请立即联系客服(微信: zhuanzhi02,邮箱:bd@zhuanzhi.ai),我们会尽快为您处理
相关内容
CVPR 2022
关注
39
CVPR 2022 将于2022年 6 月 21-24 日在美国的新奥尔良举行。CVPR是IEEE Conference on Computer Vision and Pattern Recognition的缩写,即IEEE国际计算机视觉与模式识别会议。该会议是由IEEE举办的计算机视觉和模式识别领域的顶级会议,会议的主要内容是计算机视觉与模式识别技术。
知识荟萃
精品入门和进阶教程、论文和代码整理等
更多
查看相关VIP内容、论文、资讯等
计算体系架构研究综述与思考
专知会员服务
65+阅读 · 2022年3月21日
13个经典CNN架构比较分析!从AlexNet到ResNet再到ConvNeXt
专知会员服务
101+阅读 · 2022年3月14日
【ICML2021】深度核过程
专知会员服务
25+阅读 · 2021年8月11日
【ICCV2021】深度神经网络结构解耦
专知会员服务
23+阅读 · 2021年8月1日
【MIT经典书】计算机科学数学,918页pdf
专知会员服务
114+阅读 · 2021年6月23日
【ICML2021】 突破图神经网络中消息传递的限制
专知会员服务
40+阅读 · 2021年6月10日
【ICML2021】学会用长序列记忆来排练
专知会员服务
15+阅读 · 2021年6月4日
【经典书】计算理论导论,482页pdf
专知会员服务
84+阅读 · 2021年4月10日
再登Nature!清华首次提出「类脑计算完备性」及计算系统层次结构
专知会员服务
67+阅读 · 2020年10月17日
无所不能的Self-Attention!洛桑理工ICLR2020论文验证「自注意力可以表达任何CNN卷积滤波层」
专知会员服务
56+阅读 · 2020年1月12日
王怀民院士:图灵计算模型仍是最深刻的理论基础,是新科学基础的基点
机器之心
0+阅读 · 2022年2月5日
虚数有物理意义:中科大潘建伟、南科大范靖云团队首次实验排除实数形式的标准量子力学
机器之心
0+阅读 · 2022年1月31日
输入梯度惩罚与参数梯度惩罚的一个不等式
PaperWeekly
0+阅读 · 2021年12月27日
我的猫居然是图灵机?!
量子位
0+阅读 · 2021年11月27日
里程碑!蛋白质电路实现精准控制,为纳米计算机奠定基础
学术头条
0+阅读 · 2021年11月19日
印度天才数学家拉马努金留下的3000+神奇公式,交给AI来「证明」!
新智元
0+阅读 · 2021年2月4日
一文搞懂反向传播
机器学习与推荐算法
18+阅读 · 2020年3月12日
卷积神经网络四种卷积类型
炼数成金订阅号
18+阅读 · 2019年4月16日
CNN 反向传播算法推导
统计学习与视觉计算组
30+阅读 · 2017年12月29日
python文本相似度计算
北京思腾合力科技有限公司
24+阅读 · 2017年11月6日
计算可靠且可组合安全的复杂密码协议符号化分析方法研究
国家自然科学基金
0+阅读 · 2013年12月31日
量子熵理论的若干数学问题
国家自然科学基金
0+阅读 · 2013年12月31日
绝热计算的几个关键问题研究
国家自然科学基金
1+阅读 · 2013年12月31日
柱形区域上变系数椭圆方程Cauchy问题的数值计算
国家自然科学基金
0+阅读 · 2011年12月31日
组合、设计与代数学术研讨会
国家自然科学基金
4+阅读 · 2011年8月31日
有限制条件的几何定理机器证明
国家自然科学基金
0+阅读 · 2009年12月31日
分布参数系统的H-无穷控制理论
国家自然科学基金
0+阅读 · 2009年12月31日
基于三维场计算和多值逻辑的模拟计算研究
国家自然科学基金
0+阅读 · 2009年12月31日
全纯函数空间上的复合算子理论研究
国家自然科学基金
0+阅读 · 2009年12月31日
不等式基础理论公理化研究与不等式机器证明
国家自然科学基金
0+阅读 · 2009年12月31日
Isogeometric Analysis of Acoustic Scattering using Infinite Elements
Arxiv
0+阅读 · 2022年4月20日
Modeling and Executing Production Processes with Capabilities and Skills using Ontologies and BPMN
Arxiv
0+阅读 · 2022年4月20日
Functional Covering of Point Processes
Arxiv
0+阅读 · 2022年4月20日
String Diagram Rewrite Theory III: Confluence with and without Frobenius
Arxiv
0+阅读 · 2022年4月18日
U-Net and its variants for Medical Image Segmentation : A short review
Arxiv
0+阅读 · 2022年4月17日
On an interior-exterior nonoverlapping domain decomposition method for the Poisson--Boltzmann equation
Arxiv
0+阅读 · 2022年4月17日
A Guidance and Maneuvering Control System Design with Anti-collision Using Stream Functions with Vortex Flows for Autonomous Marine Vessels
Arxiv
0+阅读 · 2022年4月16日
On the Convergence of Differentially Private Federated Learning on Non-Lipschitz Objectives, and with Normalized Client Updates
Arxiv
0+阅读 · 2022年4月16日
Fast Sparse Decision Tree Optimization via Reference Ensembles
Arxiv
0+阅读 · 2022年4月14日
Distributed Machine Learning on Mobile Devices: A Survey
Arxiv
35+阅读 · 2019年9月18日
VIP会员
自助开通(推荐)
客服开通
详情
相关主题
CVPR 2022
单元
天马
输出
话题
相关VIP内容
计算体系架构研究综述与思考
专知会员服务
65+阅读 · 2022年3月21日
13个经典CNN架构比较分析!从AlexNet到ResNet再到ConvNeXt
专知会员服务
101+阅读 · 2022年3月14日
【ICML2021】深度核过程
专知会员服务
25+阅读 · 2021年8月11日
【ICCV2021】深度神经网络结构解耦
专知会员服务
23+阅读 · 2021年8月1日
【MIT经典书】计算机科学数学,918页pdf
专知会员服务
114+阅读 · 2021年6月23日
【ICML2021】 突破图神经网络中消息传递的限制
专知会员服务
40+阅读 · 2021年6月10日
【ICML2021】学会用长序列记忆来排练
专知会员服务
15+阅读 · 2021年6月4日
【经典书】计算理论导论,482页pdf
专知会员服务
84+阅读 · 2021年4月10日
再登Nature!清华首次提出「类脑计算完备性」及计算系统层次结构
专知会员服务
67+阅读 · 2020年10月17日
无所不能的Self-Attention!洛桑理工ICLR2020论文验证「自注意力可以表达任何CNN卷积滤波层」
专知会员服务
56+阅读 · 2020年1月12日
热门VIP内容
开通专知VIP会员 享更多权益服务
军用数据链:武器装备神经,联合作战基石,31页pdf
【ETHZ博士论文】超越像素深度:通过深度学习增强超分辨率技术,198页pdf
2018∼2023年国家自然科学基金人工智能学科人才项目申请及资助综述
【NeurIPS2024】《AmoebaLLM:构建任意形状的大型语言模型以实现高效和即时部署》
相关资讯
王怀民院士:图灵计算模型仍是最深刻的理论基础,是新科学基础的基点
机器之心
0+阅读 · 2022年2月5日
虚数有物理意义:中科大潘建伟、南科大范靖云团队首次实验排除实数形式的标准量子力学
机器之心
0+阅读 · 2022年1月31日
输入梯度惩罚与参数梯度惩罚的一个不等式
PaperWeekly
0+阅读 · 2021年12月27日
我的猫居然是图灵机?!
量子位
0+阅读 · 2021年11月27日
里程碑!蛋白质电路实现精准控制,为纳米计算机奠定基础
学术头条
0+阅读 · 2021年11月19日
印度天才数学家拉马努金留下的3000+神奇公式,交给AI来「证明」!
新智元
0+阅读 · 2021年2月4日
一文搞懂反向传播
机器学习与推荐算法
18+阅读 · 2020年3月12日
卷积神经网络四种卷积类型
炼数成金订阅号
18+阅读 · 2019年4月16日
CNN 反向传播算法推导
统计学习与视觉计算组
30+阅读 · 2017年12月29日
python文本相似度计算
北京思腾合力科技有限公司
24+阅读 · 2017年11月6日
相关基金
计算可靠且可组合安全的复杂密码协议符号化分析方法研究
国家自然科学基金
0+阅读 · 2013年12月31日
量子熵理论的若干数学问题
国家自然科学基金
0+阅读 · 2013年12月31日
绝热计算的几个关键问题研究
国家自然科学基金
1+阅读 · 2013年12月31日
柱形区域上变系数椭圆方程Cauchy问题的数值计算
国家自然科学基金
0+阅读 · 2011年12月31日
组合、设计与代数学术研讨会
国家自然科学基金
4+阅读 · 2011年8月31日
有限制条件的几何定理机器证明
国家自然科学基金
0+阅读 · 2009年12月31日
分布参数系统的H-无穷控制理论
国家自然科学基金
0+阅读 · 2009年12月31日
基于三维场计算和多值逻辑的模拟计算研究
国家自然科学基金
0+阅读 · 2009年12月31日
全纯函数空间上的复合算子理论研究
国家自然科学基金
0+阅读 · 2009年12月31日
不等式基础理论公理化研究与不等式机器证明
国家自然科学基金
0+阅读 · 2009年12月31日
相关论文
Isogeometric Analysis of Acoustic Scattering using Infinite Elements
Arxiv
0+阅读 · 2022年4月20日
Modeling and Executing Production Processes with Capabilities and Skills using Ontologies and BPMN
Arxiv
0+阅读 · 2022年4月20日
Functional Covering of Point Processes
Arxiv
0+阅读 · 2022年4月20日
String Diagram Rewrite Theory III: Confluence with and without Frobenius
Arxiv
0+阅读 · 2022年4月18日
U-Net and its variants for Medical Image Segmentation : A short review
Arxiv
0+阅读 · 2022年4月17日
On an interior-exterior nonoverlapping domain decomposition method for the Poisson--Boltzmann equation
Arxiv
0+阅读 · 2022年4月17日
A Guidance and Maneuvering Control System Design with Anti-collision Using Stream Functions with Vortex Flows for Autonomous Marine Vessels
Arxiv
0+阅读 · 2022年4月16日
On the Convergence of Differentially Private Federated Learning on Non-Lipschitz Objectives, and with Normalized Client Updates
Arxiv
0+阅读 · 2022年4月16日
Fast Sparse Decision Tree Optimization via Reference Ensembles
Arxiv
0+阅读 · 2022年4月14日
Distributed Machine Learning on Mobile Devices: A Survey
Arxiv
35+阅读 · 2019年9月18日
大家都在搜
PRML
壁画
大型语言模型
ETHZ博士论文
时间序列
智能推荐
洛克菲勒
汽车智能化
无人艇
出海产品从 0 到 1 该怎么做
Top
提示
微信扫码
咨询专知VIP会员与技术项目合作
(加微信请备注: "专知")
微信扫码咨询专知VIP会员
Top