求助 计算理论的题

ioiwinUID: 183956

47. Let M be a single-tape, deterministic Turing machine with tape alphabet {blank,0,1}, and let C denote the
(possibly infinite) computation of M starting with a blank tape. The input to each problem below is M, together
with a positive integer n. Which of the following problems is (are) decidable?
I. The computation C lasts for at least n steps.
II. The computation C lasts for at least n steps, and M prints a 1 at some point after the nth step.
III. M scans at least n distinct tape squares during the computation C.
(A) None
(B) III only
(C) I and II only
(D) I and III only
(E) I, II, and III

知道一点图灵机的知识，但不知道里面说的是虾米阿。

61. Which of the following problems is (are) decidable?
I. Given a (finite) string w, is w a prefix of the decimal expansion of p ?
II. Given a program and an input, is the program’s output the decimal expansion of p ?
III. Given a program that takes as input a prefix of the decimal expansion of p, is the program’s output always
the same for every prefix?
(A) I only
(B) II only
(C) III only
(D) I and II only
(E) I, II, and III

这个也是一样的阿 ，只会判断一些简单得题，变一变就不知道了。计算理论没学过，看了很久也弄不明白，痛苦ing。

yuren78UID: 2111432

我也不行, 但可以Share my thoughts with you.

1> The key difference between "Decidable" and " NOT decidable" is to check whether the turing machine will loop on some input.

Accept or Reject both are good for "Decidable". The worst thing is loop on the input, so you don't know what it will lead to.

I> is decidable because you will know the answers after n steps. C either lasts, or not lasts.

II> M prints a 1 at some point after nth step, this is not decidable, since it may take
1 billion year to print a 1, and you are dead at that time, so is mine, so it's undecidalbe.

III> The total number configuration states of a turing machine is finite, so you will be able to know if it scans at least n steps or not.

Think about 61 yourself.

Don't worry, there are 70 questions, as long as you got 50 correct, you are well above 90%

ioiwinUID: 183956

多 谢 了 ， 有 收获

marffinUID: 171144

有一点疑问

lasts for at least n steps 说明至少执行N步，但不知道是不是执行N步之后就结束了，也不知道是不是进入了循环或者什么的，怎么说是decidable呢？

youarestupidUID: 2123815

人家的问题问的是：计算是否可以持续n步，如果计算持续小于n步就停机了，则这个问题的答案就是否；如果该计算运行到n步了，则这个问题就是yes。至于TM停不停机，不是该问题所关心的，所以该问题是decidable。

其实就是用一个TM（TM1）检查另一个TM（TM2）能否运行n步的问题，至于TM2停不停机，TM1并不关心

youarestupidUID: 2123815

61. Which of the following problems is (are) decidable?
I. Given a (finite) string w, is w a prefix of the decimal expansion of p ?
II. Given a program and an input, is the program’s output the decimal expansion of p ?
III. Given a program that takes as input a prefix of the decimal expansion of p, is the program’s output always the same for every prefix?

I是问finite串是否为某十进制数的前缀，有限串当然是decidable
II给程序一个输入，注意program就是算法，肯定有输出结果。问这个输出结果是否为十进制表示数。这个输出结果是finite，同I，也是decidable
III程序有无穷个输入和无穷个输出，判定infinite个输出是否相同，是undecidable