分享本周所学——停机问题与可计算性

2023-10-23 08:40

本文主要是介绍分享本周所学——停机问题与可计算性,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

        大家好,欢迎来到《分享本周所学》第七期。本人是一名人工智能初学者,刚刚大一。大一学校里学的课程主要还是偏理论方面的,我感兴趣的人工智能方面的课程到大二才会开,所以目前只能自己瞎搞搞研究,最近在做点AI作曲之类的项目。最近学校在学关于停机问题的一些分析。停机问题是个挺经典的问题,我觉得还挺有意思的,就想和大家分享一下。

        读懂这篇文章需要你知道任意一个语言的基本语法并了解循环结构。

目录

啥是停机问题啊

1. 停机问题的定义

2. 停机问题的分析

3. 停机问题的意义与重要性

4. 我个人对于停机问题的思考


上期文章链接:

分享本周所学——概率论:贝叶斯更新详解

本期封面:


啥是停机问题啊

        不知道大家有没有遇到过这样的问题:编程的时候写一个while循环,然后忘了在循环里面给循环变量赋值了,结果导致程序陷入死循环了,永远都停不下来。这个时候我们一般需要手动让程序停下来。我在刚接触编程那会老是犯这种错误。停机问题就和这种程序进入死循环的情况有很大的关联。

1. 停机问题的定义

        为了解决程序可能陷入死循环的问题,我们希望存在一个能够判断程序是否会进入死循环的程序。我们定义这个用来判断一个程序是否会进入死循环的程序为程序P。对于任意程序p和输入i而言,P(p,i)可能返回两个结果:true和false。如果返回结果为true,代表如果在运行程序p时将i作为输入,那么程序p会陷入死循环;如果为false,则代表p不会陷入死循环。

        现在我们定义另一个程序P^+。假设有一个程序p可以接收一个程序作为输入,那么它就可以将自己作为自己的输入(这在现实中是可行的,比如Pascal的编译器可以用Pascal来书写)。对于这样的一个程序p,我们调用P(p,p)。如果P(p,p)为true,那么P^+(p)会强制终止程序执行;如果P(p,p)为false,P^+(p)会执行一个死循环。P+可以用以下代码来表示:  

# P_plus.py
import sysdef P(p, i):# 判断将i输入程序p是否会导致死循环passif __name__ == '__main__':# 读取程序pif P(p, p):sys.exit()while True:continue
// P_plus.cpp
bool P(char* p, char* i) {// 判断将i输入程序p是否会导致死循环
}int main() {// 读取程序pif (P(p, p))return 0;while (true)continue;
}

        那现在问题来了,如果将P^+输入P^+,会发生什么呢?也就是说,P^+ \left ( P^+ \right )会得到什么运行结果?

2. 停机问题的分析

        想要知道P^+ \left ( P^+ \right )的执行结果,我们需要先知道P \left ( P^+ , P^+ \right )的执行结果。我们假设P \left ( P^+ , P^+ \right )为true,也就是说,P^+ \left ( P^+ \right )会导致P^+陷入死循环。这时,我们会强制终止运行,这样一来,P^+就不会陷入死循环了,这与上面说到的P^+ \left ( P^+ \right )导致P^+陷入死循环矛盾。

        如果我们假设P \left ( P^+ , P^+ \right )为false,也就是P^+ \left ( P^+ \right )不会导致P^+陷入死循环,那么P^+就会执行一个死循环,这与上面说的P^+ \left ( P^+ \right )不会导致P^+陷入死循环矛盾。

        因此,无论如果,这个程序在运行过程中都会产生自相矛盾的结果,那么我们就可以得到一个结论:程序P,也就是判断一个程序是否进入死循环的程序,是不存在的。

3. 停机问题的意义与重要性

        停机问题给人的感觉就像一个程序员版的理发师悖论。那这个问题除了好玩之外,能不能说明什么问题呢?

        我认为停机问题说明的最主要的问题就是,计算机并不是无所不能的。自从上世纪40、50年代,人们用错综的电子管和磁带编织成世界上最初的一批计算机开始,人类的计算机技术就在以极快的速度不断发展。如果有一天,极为精巧的电路设计和皮米甚至飞米级别的制造工艺使得计算机的储存空间和运算速度达到几乎无限,到那时,计算机能解决宇宙中的一切问题吗?答案是否定的,停机问题就是一个很好的反例。

        这也引入了计算机领域一个很重要的概念——可计算性。一个问题是否是“可计算的”,取决于它能否用计算机来解决。我们这里讨论的停机问题,就是一个不可计算的问题。

4. 我个人对于停机问题的思考

        以下纯属个人有感而发,而且纯属瞎想,不想看的话可以跳过(指直接去结尾给我点赞)。

        我们来思考这样一个问题:人类是否能够判断一个程序是否会陷入死循环?

        这个问题似乎让停机问题变得更加哲学了。稍微思考一下,人类似乎可以判断一个程序是否会陷入死循环。对于一些简单的程序,比如C++中的“while (true) continue;”,我们一眼就看出来这必然是个死循环。对于稍微复杂一点的程序,我们稍微研究分析一下,也能给出一个正确的结论。

        但是人类是怎么思考的呢?人类的思考是通过人脑中的几百亿个神经元互相连接,通过几十种神经递质传递信息来完成的。然而,每一个神经元的运作方式都是固定的,现代的神经科学也已经对单个神经元的运作方式有了比较透彻的了解。那么,我们是不是也可以推断,大脑中的几百亿个神经元互相连接,它们作为一个整体的运作方式也是固定的?换句话说,我们人类的运作方式,是不是也是固定的?如果真是这样,那么人类是不是和计算机没有区别?

        我们甚至也可以把人类看作一种程序,我们接收的输入来自自然环境,比如光线、声波以及我们接触和摄入的各种物质,而我们的大脑会根据一个固定的机制对这些输入作出回应。

        再回到刚才的问题。假设我们把“人类判断一个程序是否会陷入死循环”这一过程称为过程P,把人类在阅读一个程序时接收到的一系列视觉信号称为p,把被判断的程序接收到的输入称为i,那么P(p,i)是有解的吗?

        这就交给各位来思考了。

这篇关于分享本周所学——停机问题与可计算性的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/266742

相关文章

Ilya-AI分享的他在OpenAI学习到的15个提示工程技巧

Ilya(不是本人,claude AI)在社交媒体上分享了他在OpenAI学习到的15个Prompt撰写技巧。 以下是详细的内容: 提示精确化:在编写提示时,力求表达清晰准确。清楚地阐述任务需求和概念定义至关重要。例:不用"分析文本",而用"判断这段话的情感倾向:积极、消极还是中性"。 快速迭代:善于快速连续调整提示。熟练的提示工程师能够灵活地进行多轮优化。例:从"总结文章"到"用

【专题】2024飞行汽车技术全景报告合集PDF分享(附原数据表)

原文链接: https://tecdat.cn/?p=37628 6月16日,小鹏汇天旅航者X2在北京大兴国际机场临空经济区完成首飞,这也是小鹏汇天的产品在京津冀地区进行的首次飞行。小鹏汇天方面还表示,公司准备量产,并计划今年四季度开启预售小鹏汇天分体式飞行汽车,探索分体式飞行汽车城际通勤。阅读原文,获取专题报告合集全文,解锁文末271份飞行汽车相关行业研究报告。 据悉,业内人士对飞行汽车行业

java常用面试题-基础知识分享

什么是Java? Java是一种高级编程语言,旨在提供跨平台的解决方案。它是一种面向对象的语言,具有简单、结构化、可移植、可靠、安全等特点。 Java的主要特点是什么? Java的主要特点包括: 简单性:Java的语法相对简单,易于学习和使用。面向对象:Java是一种完全面向对象的语言,支持封装、继承和多态。跨平台性:Java的程序可以在不同的操作系统上运行,称为"Write once,

分享5款免费录屏的工具,搞定网课不怕错过!

虽然现在学生们不怎么上网课, 但是对于上班族或者是没有办法到学校参加课程的人来说,网课还是很重要的,今天,我就来跟大家分享一下我用过的几款录屏软件=,看看它们在录制网课时的表现如何。 福昕录屏大师 网址:https://www.foxitsoftware.cn/REC/ 这款软件给我的第一印象就是界面简洁,操作起来很直观。它支持全屏录制,也支持区域录制,这对于我这种需要同时录制PPT和老师讲

【干货分享】基于SSM的体育场管理系统的开题报告(附源码下载地址)

中秋送好礼 中秋佳节将至,祝福大家中秋快乐,阖家幸福。本期免费分享毕业设计作品:《基于SSM的体育场管理系统》。 基于SSM的体育场管理系统的开题报告 一、课题背景与意义 随着全民健身理念的深入人心,体育场已成为广大师生和社区居民进行体育锻炼的重要场所。然而,传统的体育场管理方式存在诸多问题,如资源分配不均、预约流程繁琐、数据统计不准确等,严重影响了体育场的使用效率和用户体验。

图书管理系统系统分享

分享一个图书管理系统,Java、SpringBoot、Vue和MySQL开发的图书馆管理系统 gitee项目地址:https://gitee.com/yuanmomoya/open-source-project/tree/master/books-management-system GitHub项目地址:https://github.com/yuanmomoya/open-source-pro

站长常用Shell脚本整理分享(全)

站长常用Shell脚本整理分享 站长常用Shell脚本整理分享1-10 站长常用Shell脚本整理分享11-20 站长常用Shell脚本整理分享21-30 站长常用Shell脚本整理分享31-40 站长常用Shell脚本整理分享41-50 站长常用Shell脚本整理分享51-59 长期更新

分享MSSQL、MySql、Oracle的大数据批量导入方法及编程手法细节

1:MSSQL SQL语法篇: BULK INSERT      [ database_name . [ schema_name ] . | schema_name . ] [ table_name | view_name ]         FROM 'data_file'        [ WITH       (      [ [ , ] BATCHSIZE = batch_siz

分享一个基于uniapp科技馆服务微信小程序 博物馆管理小程序(源码、调试、LW、开题、PPT)

💕💕作者:计算机源码社 💕💕个人简介:本人 八年开发经验,擅长Java、Python、PHP、.NET、Node.js、Android、微信小程序、爬虫、大数据、机器学习等,大家有这一块的问题可以一起交流! 💕💕学习资料、程序开发、技术解答、文档报告 💕💕如需要源码,可以扫取文章下方二维码联系咨询 💕💕Java项目 💕💕微信小程序项目 💕💕Android项目 �

2024年 Biomedical Signal Processing and Control 期刊投稿经验最新分享

期刊介绍 《Biomedical Signal Processing and Control 》期刊旨在为临床医学和生物科学中信号和图像的测量和分析研究提供一个跨学科的国际论坛。重点放在处理在临床诊断,患者监测和管理中使用的方法和设备的实际,应用为主导的研究的贡献。 生物医学信号处理和控制反映了这些方法在工程和临床科学的界面上被使用和发展的主要领域。期刊的范围包括相关的评论论文(review p