t****n
发帖数: 56 | 1 关键是你如何定义并行，Dijikstra给了个狭义的定义，即并行的部分可以
按任意次序排列指令，结果等价。在编译理论方面有很多理论上的研究，
考虑时间和空间的变换不变性等。 | l*c
发帖数: 1 | 2 并行计算的能力不会超过图灵机， 因此一定可以用单CPU模拟
其实直觉上并行性并不能提供高于递归函数的能力，任何属于
递归可枚举(且非递归）或其上的函数（语言）直觉上在加入并行性后仍
不可计算，各种不可计算的判定问题显然不可能通过加入
并行性来解决 | h****g
发帖数: 56 | 3
是的
图灵机可从不考虑什么时间片的问题, 所谓计算的能力是指能
不能识别某类语言, 不存在误差的概念. 假如你考虑计算步数
的话, 用单带图灵机模拟多带图灵机当然要慢. 但从可计算性
角度看是一样的. | w**n
发帖数: 88 | 4
Yes , In the theory of computation it is called : Mulititape Turing Machine is
equivalent with an single tape Turing machine.the multitape here means that
Turing machine has the ability of parallel computing
It seems you are not considering a computability problem, so you need to
define clearly what the meaning of 能力 here is. | s*a
发帖数: 33 | 5 In theory that maybe true, but in practice there do exist "superlinear
speedup", that is, the total time of parallel computation is less than
that of a single processor. One of the common reason for this is the
resources for a single processor is limited (in practice), while going
parallel, more resources are allowed to be accessed. For example, more
cache can be used in a parallel environment. This is quite similar
to your analogy of 三个臭皮匠, 顶个诸葛亮. :) Each head's "thinking"
resources is limited, | t**********e
发帖数: 254 | 6 Specialized improved ability and productivity. This is true for human beings
【在 w**n 的大作中提到】
:
: Yes , In the theory of computation it is called : Mulititape Turing Machine is
: equivalent with an single tape Turing machine.the multitape here means that
: Turing machine has the ability of parallel computing
: It seems you are not considering a computability problem, so you need to
: define clearly what the meaning of 能力 here is.
|
|
