面试官偶然问出了曾经困扰了世界几十年的问题

本来是关于devops的一个很小的环节, 问题就是, 对程序进行静态分析 那么你能否知道程序中是否存在死循环?



我一下子就兴奋了说这个问题好啊 我正好学过可计算性理论, 你在说的是大名鼎鼎的停机问题, 是这个学科的根基, 本质上来讲就是是否存在一个程序x, 判断程序y是否可以在有限时间内结束或者永远继续下去(也即死循环)

我说答案是不行, 并且跟他解释了停机问题的解, 他在构造自我指涉那一步就一脸cpu烧了的表情, 我都没敢讲什么一阶逻辑不完备性之类的话, 感觉他估计没听到或者觉得我在框他....毕竟本来是一个很愉快的云工程师面试在他问出这个问题后画风突然就硬核了起来

补一个停机问题的wiki
https://zh.wikipedia.org/zh-hans ... A%E9%97%AE%E9%A2%98

同志们做面试官的话千万别问自己不知道的问题啊....

面试时候，最佳策略是用对方能理解的语言和他讨论，而不要炫耀知识。毕竟对方要找的是未来一起工作的人。

补充内容 (2023-02-08 02:52 +08:00):
补充：当然稍微说一点可以。注意看对方反应。但是一定确保自己真的知道。否则万一对方是大拿就弄巧成拙了。浅尝辄止的东西别拿出来炫。

我觉得面试还是避免炫耀知识的好，该回答啥回答啥，不要把话题引入自己擅长的领域然后让别人一脸懵逼。

首先要正确回答问题，这是技术考核。

面试还有软实力考核，culture fit。
说白话就是我会不会愿意和这个求职者每天一起喝杯咖啡，或者每天让我和这个人一起开会我会不会觉得舒服。

要是再给楼主45分钟，咱下一步还能向他销售 Type Theory 以及 Idris 的应用

又回想起了被图灵机支配的恐惧……

你能否知道和程序能否知道还是不一样的，还是别自作聪明了。
良定义和可计算是两个事情。

waterfall 发表于 2023-02-07 01:16:56
你能否知道和程序能否知道还是不一样的，还是别自作聪明了。
良定义和可计算是两个事情。

的确是没有 只能使用保守的方法例如Foetus分析或者设置超时等 但局限性非常大 因此静态分析并不包含任何死循环检查

面试官会不会只想检查一下for (;;)或者while (true)，关注的是代码风格，而不是可计算理论。。

匿名用户 发表于 2023-02-07 01:44:52
面试官会不会只想检查一下for (;;)或者while (true)，关注的是代码风格，而不是可计算理论。。

其实我一开始给出的就是foetus和超时 但这俩都是动态的 静态分析的确没有任何办法对于一个给定输入的循环进行检查 然后面试官很有兴趣的跟我探讨这个问题就变成数学讨论了....

匿名用户 发表于 2023-02-07 01:44:52
面试官会不会只想检查一下for (;;)或者while (true)，关注的是代码风格，而不是可计算理论。。

如果是devops，对方可能问的是比如build validation过程中可以用的办法来避免一些浅显的死锁，比如你说的空的while body。

停机问题是不存在通用算法，具体的问题还是有很多在工程上有意义的探索的。这方面研究有很多。

楼主既然这么不珍惜面试机会何苦浪费彼此的时间。