|
以文本方式查看主题 - 计算机科学论坛 (http://bbs.xml.org.cn/index.asp) -- 『 理论计算机科学 』 (http://bbs.xml.org.cn/list.asp?boardid=64) ---- 一个刁钻的问题：有单指令计算机吗？ (http://bbs.xml.org.cn/dispbbs.asp?boardid=64&rootid=&id=52683) |
|
-- 作者：libinw -- 发布时间：9/15/2007 5:44:00 PM -- 一个刁钻的问题：有单指令计算机吗？ 我是搞经济理论的；出于本专业考虑，希望请教各位计算机专家一个问题：理论上可以有“单指令”计算机吗，即只有一个指令，是否可以完成现有计算机的全部计算任务？不考虑计算时间问题。哪位高手指点？该问题对社会科学理论有重大意义，谢谢！ 李斌 |
|
-- 作者：libinw -- 发布时间：9/16/2007 9:11:00 AM -- 或者，计算机指令的数目理论上不得少于几个？ 或者，计算机指令的数目理论上不得少于几个？谢谢！李斌 |
|
-- 作者：triones -- 发布时间：11/6/2007 11:13:00 PM -- 我尝试着回答一下你的问题，我记得在离散数学中有个完备集的概念，由于我学这门课程已经很长时间了，我只能大概说一下，所谓完备集好象指的是用某几个逻辑运算符号就可以完全推导出其它所有运算符号的功能，比如使用~（非运算）、与运算，或运算（打不出来符号，对付看吧），用这三个运算符号就可以实现—>和<——>的功能，因此说非运算、与运算和或运算是完备的。同样，单独一个非运算就是不完备的。推断到你的问题，我个人认为单一指令是不完备的，也就是说，不可能有单一指令的计算机实现目前多指令计算的能实现的功能，当然，这是我个人的推断，规范化的在证明我还给不出，不一定正确，供参考 |
|
-- 作者：libinw -- 发布时间：11/7/2007 9:10:00 AM -- 谢谢。不过... 非常感谢。虽然不同计算机的指令数目并不相同，看来显然指令存在一个最低的数目；指令数不得少于这个数目。不过仍然不知道这个数目应为多少？它应包含什么样的指令？ |
|
-- 作者：wu5zg -- 发布时间：11/12/2007 9:52:00 AM -- 按照自动机等价的理论中，貌似图灵机就是能够识别0型语言的最简单的计算模型了，但是一条指令肯定是不行的的，但是主要是搞不清啥算是一条指令 |
|
-- 作者：奸神 -- 发布时间：11/29/2007 2:13:00 AM -- 我来说说我的想法吧 指令有微指令和指令（计算机组成原理），一个指令包含了N个微指令 照这样看来，我们或者可以将一个函数看成是一个指令，然后一个函数包含了N个微指令 于是，到底是否存在单指令的计算机呢？ 假设这个函数包含了很多很多个参数，假设为M，把实际上所有可能出现的参数都包含在里面，然后针对每种不同的参数组合执行不同的过程。假设每个参数有K种可能的取值，当然如果是数值的话是有无数种的（跟计算机字节长度有关），那么共有K^M种可能的组合。大家都知道，只要M足够大，那么这个数字甚至可以包含宇宙的任何事物。 也就是说，将这个函数看成是一个指令，针对现在世界上计算机所实现的所有功能进行设计，当然它是可数并有限的，那么我们就可以实现单指令计算机。 |
|
-- 作者：wu5zg -- 发布时间：11/29/2007 11:21:00 AM -- 你这个实际上是一个M元函数，可以用一个有M个输入的电路实现，你这里面可能偷换了通常大家说的计算机指令的概念。事实上，指令应该对应的是这个电路的输入。极端的情况，M可以就是可数无穷个。换句话说，你那个应该相当于最多有M的冪集个指令，应该是无穷不可数的，比可数无穷要大得多。 |
|
-- 作者：libinw -- 发布时间：11/29/2007 4:30:00 PM -- 让我再来说明一下我的问题 假设就ＩＮＴＥＬ８０８６／８０８８机型而言，它提供了几十个指令, 作为硬件与软件的接口; 由于一定的硬件功能可以用软件来实现, 比如乘法可以用加法的程序化作业方式来实现, 那么指令清单中的"乘法"指令就可以删去. 现在按照这个思路来精简指令清单,尽可能减少所使用指令的种类, 而程序长度不限, 那么, 这样简化下去, 最终得到的、不能再简化的指令数目是多少？这些最基本的指令又是什么？当然，前提是，这样的计算机可以执行ＩＮＴＥＬ８０８６／８０８８机型的任何功能，只是运算时间会大大延长。这样的问题成立吗？请各位高手继续给予指点，谢谢！ |
|
-- 作者：wu5zg -- 发布时间：11/30/2007 9:42:00 AM -- 因为计算机可以处理的是原始递归的函数，所以感觉上应该至少有加法和计数就可以 |
|
-- 作者：libinw -- 发布时间：11/30/2007 2:36:00 PM -- 我同意,但是... 谢谢。就代数运算来说,我同意这个观点；当然还有逻辑运算，以及一些功能性指令，因此似乎还应当有进一步的答案 |
|
-- 作者：奸神 -- 发布时间：12/6/2007 1:39:00 AM -- 实际上计算机是由许多的与或非门组成的 所以从3楼所说的来看 确实只要能给出完备集，就可以实现所有的功能 从这个角度来看的话，只要能给出逻辑运算的完备集就可以实现所有的功能 而最少的完备集就是（非，与）或者（非，或），仅需要两个指令 |
|
-- 作者：奸神 -- 发布时间：12/6/2007 1:52:00 AM -- 查了一下课本 典型指令包括 数据传送指令 算术运算指令 逻辑运算指令 程序控制指令 输入输出指令 字符串处理指令 特权指令 其他指令 每种指令下又包含了不同的指令 比较典型的有CISC（复杂指令系统）和RISC（精简指令系统） 课本上列出的RISC-I包含了31个指令 |
|
-- 作者：Logician -- 发布时间：12/6/2007 8:23:00 PM -- 最小的完备集只需要一个联结词。 |
|
-- 作者：se98 -- 发布时间：12/9/2007 4:12:00 PM -- 个人认为可以。 计算机只有一条指令，叫做：OPR。 其他操作全部以操作数形式出现。 opr add ax,bx opr mov ds,ax ... 即把所有指令看做一条指令。 |
|
-- 作者：affe -- 发布时间：12/14/2007 5:48:00 AM -- 关键是加法就是与或电路门实现的吧，按题意应该被删去 有不用与或电路门，能实现加法的硬件吗？ 与非 或者 或非肯定能搞定所有的。
|
|
-- 作者：affe -- 发布时间：12/14/2007 5:51:00 AM -- 图林机中怎么定义一条指令 有多少种不同的状态吗？就算几条指令？
[此贴子已经被作者于2007-12-14 6:23:49编辑过]
|
|
-- 作者：mumuok -- 发布时间：2/20/2008 4:58:00 PM -- 最小的完备集只需要一个联结词?为什么? |
|
-- 作者：llllll -- 发布时间：3/2/2008 2:20:00 PM -- 我认为,至少应该有加法\置位\移位\条件跳转\中断5条指令,才有可能实现INTEL8086/8088的相关运算处理功能. |
|
-- 作者：ruankefeng -- 发布时间：4/29/2008 3:43:00 PM -- 有的， 我在 浙大 版本的 计算机组成设计 书上看到过（课后习题里）， 好像是 减法指令（同时它还会判断是否为0，如果是零就跳转到另一操作数所指示的地址）。 |
|
-- 作者：yushih -- 发布时间：4/30/2008 10:49:00 AM -- 楼主你太有才了 你去年问这个问题的时候这个问题还没有答案，但是如今已经有了（如果我没有理解错的话） http://www.wolframscience.com/prizes/tm23/solved.html http://arstechnica.com/news.ars/post/20071024-simple-turing-machine-shown-capable-of-solving-any-computational-problem.html http://blog.wolfram.com/index.php?year=2007&monthnum=10&name=the-prize-is-won-the-simplest-universal-turing-machine-is-proved |
|
-- 作者：libinw -- 发布时间：4/30/2008 2:09:00 PM -- 好象是... 首先非常感谢您的信息.我粗看了一下,此人的回答似乎正是我所问的本意,不过它直接回答的好象是硬件实现方式问题,如果转换为软的指令,尚不知是什么样子......我的能力有限,这个研究成果还希望诸君共同来解读. |
|
-- 作者：tjmmjt -- 发布时间：6/29/2008 2:45:00 PM -- 这个问题也困扰我很长时间了，搜遍网络没有找到答案。我是在看到“所有的软件功能可以用硬件实现，所有的硬件功能也可以用软件在一个通用微处理器上实现”时想到这个问题的，即一个通用微处理器的最小完备指令集是什么？只要具备了这些最基本的指令，通过组合就可以实现所有其他指令的功能。由于只使用与非门就可以构成所有其他的逻辑门，进而实现任何逻辑电路，貌似只要具有与指令、非指令就可以实现所有其他指令，可是这两条指令的格式如何定义，才能进而实现存储器读写指令等等其他指令，而且可以运行这两条指令的通用微处理器的最简单结构是什么，包括哪些部件？ |
|
-- 作者：yushih -- 发布时间：6/30/2008 9:07:00 PM -- ls的同学，你的问题似乎应该用“图灵完备性”来回答。我也是初学，说不太清楚，不过你可以用这个关键词搜索，应该可以找到答案。 |
|
-- 作者：libinw -- 发布时间：7/14/2023 9:07:00 PM -- 这个问题的终极答案终于搞清楚了： “单一指令计算机”。有多种方案实现，参阅同名词条： https://www.baike.com/wikiid/4646259503781283140?view_id=476bw45jb54000 https://zh.wikipedia.org/wiki/%E5%8D%95%E4%B8%80%E6%8C%87%E4%BB%A4%E8%AE%A1%E7%AE%97%E6%9C%BA https://en.wikipedia.org/wiki/One-instruction_set_computer#References 根据其中的内容，第一个方案于1988年发表，2003年有成熟的总结性作品发表，目前最新方法是碳纳米管计算机，使用178个晶体管即可实现图灵完全性。 谢谢！ 楼主 谨启 |
|
W 3 C h i n a ( since 2003 ) 旗 下 站 点 苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》 |
117.188ms |