x****u
发帖数: 44466 | |
x****u
发帖数: 44466 | 2 用这个问题给沉迷FP的人换换脑子。
【在 x****u 的大作中提到】
: 告诉考官停机问题无解的，马上就可以闪人了。
|
E*****m
发帖数: 25615 | |
x****u
发帖数: 44466 | 4 不是稻草人，是现实问题。
【在 E*****m 的大作中提到】
: 自己樹稻草人來打，無聊！
|
E*****m
发帖数: 25615 | 5
你把這個面試的停機說一次看看。
【在 x****u 的大作中提到】
: 不是稻草人，是现实问题。
|
x****u
发帖数: 44466 | 6 放24小时以上再公布答案。
【在 E*****m 的大作中提到】
:
: 你把這個面試的停機說一次看看。
|
E*****m
发帖数: 25615 | 7 問你題目，不是答案。
【在 x****u 的大作中提到】
: 放24小时以上再公布答案。
|
x****u
发帖数: 44466 | 8 题目就是，写个程序，如何判断另一个程序能否停机。
【在 E*****m 的大作中提到】
: 問你題目，不是答案。
|
E*****m
发帖数: 25615 | 9
你給個百分之百正確解的話， 我幫你向 ACM 申請 Turing Award。
【在 x****u 的大作中提到】
: 题目就是，写个程序，如何判断另一个程序能否停机。
|
A*******t
发帖数: 443 | 10 我来猜一下，计算机其实不能算图林机，而是linear bounded machine，而判断LBA能
不能停机只要找个内存更大的LBA即可
【在 E*****m 的大作中提到】
:
: 你給個百分之百正確解的話， 我幫你向 ACM 申請 Turing Award。
|
|
|
x****u
发帖数: 44466 | 11 面试的话，你这个解答不合格，下一位。
【在 E*****m 的大作中提到】
:
: 你給個百分之百正確解的話， 我幫你向 ACM 申請 Turing Award。
|
x****u
发帖数: 44466 | 12 基本就是这个答案。
就算计算机真的是图灵机，大部分计算机语言也不等价于图灵机。所以针对具体语言
分析，还是可以判定的。
【在 A*******t 的大作中提到】
: 我来猜一下，计算机其实不能算图林机，而是linear bounded machine，而判断LBA能
: 不能停机只要找个内存更大的LBA即可
|
A*******t
发帖数: 443 | 13 我來formalize一下，
假設LBA有k個instruction，s個alphabet，長度為n的memory
然後，LBA只可能有k * n * s^n种configuration（第几条instruction，head的位置，
和memory的configuration）。
我们simulate LBA k * n * s^n 部，如果还没有停机的话，依据鸽笼原则，必然存在
起码一个loop，既然如此，必定loop forever。
【在 x****u 的大作中提到】
: 基本就是这个答案。
: 就算计算机真的是图灵机，大部分计算机语言也不等价于图灵机。所以针对具体语言
: 分析，还是可以判定的。
|
E*****m
发帖数: 25615 | 14
你這裡已經加進了一些原來沒說的假設
1. memory 是有限的 （這還算合理）
2. k*n*s^n 足夠小 （這就嚴重不合理了）
一邊是純理論假設 memory 無限， 無解，
一邊是考慮實際應用， 等太久事實上也等於無解，
只有在中間兩種情形都不是的時候才有解。
【在 A*******t 的大作中提到】
: 我來formalize一下，
: 假設LBA有k個instruction，s個alphabet，長度為n的memory
: 然後，LBA只可能有k * n * s^n种configuration（第几条instruction，head的位置，
: 和memory的configuration）。
: 我们simulate LBA k * n * s^n 部，如果还没有停机的话，依据鸽笼原则，必然存在
: 起码一个loop，既然如此，必定loop forever。
|
E*****m
发帖数: 25615 | 15 這個跟 FP 一點關係都沒有。 是CS 的基礎問題。 |
x****u
发帖数: 44466 | 16 关系很大。
比如说C/C++，就是一种即使在图灵机上停机也可以预测的语言，但大多数FP都做不到。
【在 E*****m 的大作中提到】
: 這個跟 FP 一點關係都沒有。 是CS 的基礎問題。
|
E*****m
发帖数: 25615 | 17
到。
胡扯。
我給你一個C程序，你來預測，如何？
【在 x****u 的大作中提到】
: 关系很大。
: 比如说C/C++，就是一种即使在图灵机上停机也可以预测的语言，但大多数FP都做不到。
|
x****u
发帖数: 44466 | 18 如果你觉得这个方法做不了的话，就是C没有学好：
http://mitbbs.com/article1/Programming/31243881_3_0.html
【在 E*****m 的大作中提到】
:
: 到。
: 胡扯。
: 我給你一個C程序，你來預測，如何？
|
E*****m
发帖数: 25615 | 19
我給你一個C程序，你來預測，如何？
【在 x****u 的大作中提到】
: 如果你觉得这个方法做不了的话，就是C没有学好：
: http://mitbbs.com/article1/Programming/31243881_3_0.html
|
d******r
发帖数: 5008 | 20
问这问题的，一定不是面试码农的位置。
【在 x****u 的大作中提到】
: 题目就是，写个程序，如何判断另一个程序能否停机。
|
|
|
j********x
发帖数: 2330 | 21 那我问你我现在在做啥？
这种题就跟当年流行的问厕所有多少，公交车放几个球一样，看上去精妙高深，又考察
发散思维能力；实际上这些东西对码工来说实际上又没啥重要意义；如今这种面试题都
消失了
【在 x****u 的大作中提到】
: 基本就是这个答案。
: 就算计算机真的是图灵机，大部分计算机语言也不等价于图灵机。所以针对具体语言
: 分析，还是可以判定的。
|
x****u
发帖数: 44466 | 22 扯淡，这玩意非常有现实意义！
比方说虽然静态检测代码错误和停机问题等价数学上无解，但static analysis在编程
中还是有大用处。
【在 j********x 的大作中提到】
: 那我问你我现在在做啥？
: 这种题就跟当年流行的问厕所有多少，公交车放几个球一样，看上去精妙高深，又考察
: 发散思维能力；实际上这些东西对码工来说实际上又没啥重要意义；如今这种面试题都
: 消失了
|
E*****m
发帖数: 25615 | 23
你就扯淡吧， 你給我舉出一個實際可用的 static analysis 可以測 halting problem
的。
【在 x****u 的大作中提到】
: 扯淡，这玩意非常有现实意义！
: 比方说虽然静态检测代码错误和停机问题等价数学上无解，但static analysis在编程
: 中还是有大用处。
|
j********x
发帖数: 2330 | 24 我靠，你说我扯淡了又。。。
那我问你我口袋里装上就没现实意义？我帖子里都列举了。。。
既然你看出我的问题扯淡，怎么就没看出你自己的问题扯淡。。。
【在 x****u 的大作中提到】
: 扯淡，这玩意非常有现实意义！
: 比方说虽然静态检测代码错误和停机问题等价数学上无解，但static analysis在编程
: 中还是有大用处。
|
x****u
发帖数: 44466 | 25 你少见多怪了。
用仿真器跑嵌入式内核，最后发现CPU在几个状态内循环，内存无变化的就是死锁了，
俗称跑飞了。这是常见操作。
problem
【在 E*****m 的大作中提到】
:
: 你就扯淡吧， 你給我舉出一個實際可用的 static analysis 可以測 halting problem
: 的。
|
E*****m
发帖数: 25615 | 26 你自己算算embedded 有 1MB RAM 的話你的 simulator 要有多少 RAM 才能記住狀態。
去算，我等你。
【在 x****u 的大作中提到】
: 你少见多怪了。
: 用仿真器跑嵌入式内核，最后发现CPU在几个状态内循环，内存无变化的就是死锁了，
: 俗称跑飞了。这是常见操作。
:
: problem
|
d******r
发帖数: 5008 | 27 几个状态究竟是多少状态?
循环究竟要循环几次才算飞?
【在 x****u 的大作中提到】
: 你少见多怪了。
: 用仿真器跑嵌入式内核，最后发现CPU在几个状态内循环，内存无变化的就是死锁了，
: 俗称跑飞了。这是常见操作。
:
: problem
|
x****u
发帖数: 44466 | 28 你这就是书呆子了。
人家一个程序的界限没这么大。
。
【在 E*****m 的大作中提到】
: 你自己算算embedded 有 1MB RAM 的話你的 simulator 要有多少 RAM 才能記住狀態。
: 去算，我等你。
|
x****u
发帖数: 44466 | 29 这是另外一题。
【在 d******r 的大作中提到】
: 几个状态究竟是多少状态?
: 循环究竟要循环几次才算飞?
|
d******r
发帖数: 5008 | 30 这个都不能知道，还宣称解个P的停机问题。
【在 x****u 的大作中提到】
: 这是另外一题。
|
|
|
x****u
发帖数: 44466 | 31 做不出来不要悲愤。
【在 d******r 的大作中提到】
: 这个都不能知道，还宣称解个P的停机问题。
|
E*****m
发帖数: 25615 | 32 那麼是多大？ 你舉個你認為合理的大小，算看看。
【在 x****u 的大作中提到】
: 你这就是书呆子了。
: 人家一个程序的界限没这么大。
:
: 。
|
x****u
发帖数: 44466 | 33 你可以和上面那位同学一起等等。
【在 E*****m 的大作中提到】
: 那麼是多大？ 你舉個你認為合理的大小，算看看。
|
E*****m
发帖数: 25615 | 34
你到基版去學學那位 snoopy 弟兄怎樣收場吧。
【在 x****u 的大作中提到】
: 你可以和上面那位同学一起等等。
|
