Re: [问卦] 真的可以使用0和1写程式的八卦吗?

楼主: roger29 (想不到)   2015-08-17 11:53:31
完全只用0和1理论上应该是可以,不过应该还要经过不少转换会很麻烦的吧,
但是用一些数字来写程式倒是可以的,这其实就是一个Turing Machine(图灵机)啊,
但是要用图灵机来写程式非常困难,一个简单的指令实作可能要几十甚至几百行,
既然这样为什么不去写写C或是Python之类的玩玩就好勒?
一个标准的图灵机是由硬件和软件两大部分所组成的,
硬件的部分就是一段理想上是无限长一格一格的记录带,一个记录格可以放一个symbol。
还有一个读写头,每一次读写头可以读取某格上的symbol,
还可以把这个symbol替换成别的并且选择移动方向(左右或不动)。
软件就是程式的部分啦,一个图灵机的指令大致上这样:
{current state}{current symbol}{new symbol}{movement}{new state}
一开始图灵机都是从state 0开始,而还没执行程式前你记录带上的东西就是你的input。
所以你下一个指令假如是这样:
0 _ 1 R 0
这个指令做的事就是若你的state为0且读写头指向的记录格为空(_),
则将此记录格填入new symbol也就是1,接着往右移动一格(R),
跳到新的state(还是0)。
所以应该很多人知道这一行指令码会让图灵机做什么了,
他会一直往右写1写下去,所以执行之后你的记录带看起来大概是这样:
..._ _ _ _ _ _ _ _ _ 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

读写头起点
只要写一个1的话,也很简单,只要把上面那一行改成
0 _ 1 R 1
就可以了,这一行和上面那行的差别只在new state原本是0现在是1,
当第一个记录格被写入1之后,它会跳到state 1,
但由于state 1我们没有相对应的代码,所以这个程式就停止了(halt)。
像上面这样,一些更复杂的动作可以也可以用多行指令码来实作,
不过好像还没看到怎么用数字写程式,
其实只要做一个很直观的mapping,就可以把上面一行的五个符号对应成数字了。
state:原本就是数字(0 1 2...)
symbol:假设是two-symbol的话,就是0(代表空白)和1。
movement:往左=0,往右=1,不动=2。
类似这样,就可以把0 _ 1 R 1改成00111,
虽然这样不是只用0和1来写,但是再经过几个去转换,
也是可以转成真的只用二进为来表示这段指令码。
比如先把00111用某种方式转成十进制的一个自然数,在把这个自然数用二进制表示这样。
不过大概想一下就知道,用这种方法写程式非常非常没有效率,
介绍一个网站: http://morphett.info/turing/turing.html
这是一个图灵机simulator,即你可以在这里写你的图灵机代码并用这个模拟器跑,
google搜寻Turing machine simulator也有其他类似的可以玩。
下面这段指令码拿去是把一串k个1的input变成2k个1的指令,就相当于是乘以2的动作,
0 1 2 r 1
1 1 1 r 1
1 _ 3 l 2
2 1 1 l 2
2 3 3 l 2
2 2 1 r 3
3 3 1 * 5
3 1 2 r 4
4 1 1 r 4
4 3 3 r 4
4 _ 1 l 2
有兴趣可以复制这指令码去跑跑看,假如你初始是111,跑完就会变成111111这样。
实作一个乘以2的指令码就这么复杂而且不直观,没事干麻用这玩意写程式?
然后这段可以改写成一大堆数字:
0121111111103122111223312221133312531214411144331440112
不过既然图灵机要实作这么麻烦,图灵机还有啥用勒?
举例来说,图灵机有一个优点就是它的架构非常简单(相比于我们用的电脑),
但是我们可以拿图灵机来验证很多东西,借此知道某些我们电脑的限制,
比如一个natural number to natural number的function能不能用电脑计算出来?
若图灵机可以,我们的电脑就可以,反之则不行,
而从图灵机去验证容易的多,因为它的架构非常简单,类似这种情形。
※ 引述《WeiMyWoW (...)》之铭言:
: 很久以前,那还是我用win98的时候有次我系统崩溃了,
: 因为我是电脑白吃,我朋友给我介绍了一个高手来帮我修电
: 脑。
:   
:   他看了一下电脑,问我有没有98的光盘,我说没有。
:   
:   他想了一下,叫我把固定电话拿给他,我想修电脑要电
: 话干什么,但人家是高手,我也不好说什么,就把电话拔下
: 来给他了。
:   
:   他把电话线空着的一头接在电脑的一个插孔内,然后进
: 入了dos,然后就开始在电话上不停的按著键,他按键的速度
: 非常快,但是只按0,1两个键,我搞不懂这有什么用,但也
: 不敢问,看了半个多小时,他还是不停的按这两个键,我渐
: 渐的有些困,我问他这东西要搞多久,他说要几个小时,我
: 给他倒了杯茶,就一个人去隔壁睡觉了。
:   
:   醒来的时候,一看已经过了4个多小时,我起身到隔壁,
: 看见他正在98里面调试,过了一会儿,他说,你试试,我坐
: 上椅子用了一下,真的好了,我当时也不懂电脑,谢过人
: 家就走了。
:   
:   后来我慢慢对电脑有了了解,终于了解,原来当时那位
: 高手是用机器语言编了一个98系统,我后来问我朋友那位高
: 手的下落,我朋友说前几年去了美国之后,杳无音讯....
:  
: 是说电子讯号本来就是高电位和低电位组成,也就是0和1,但真的可以拿来写程式吗?
作者: EinArthur (雷姆好可爱喔雷姆)   2015-08-17 11:54:00
嗯嗯我也是这么想ㄉ
作者: p72910 (总是有刁民想害朕)   2015-08-17 11:55:00
就是finite state machine啊 这么简单还讲这么多
作者: lainhoter   2015-08-17 11:55:00
我在教计算理论也是这样跟学生说,不过你有个字错了
作者: LFD (坏掉的LED)   2015-08-17 11:57:00
我看到原文的版本是有人拿针在光盘片上面戳
作者: leobear (雷欧)   2015-08-17 11:57:00
喔喔
作者: kopune (無限期支持 i☆Ris)   2015-08-17 11:57:00
你是 零一系?
作者: saiya (台南中肯伯)   2015-08-17 11:59:00
你是 零一士 ?
作者: chadhsieh (谢老板)   2015-08-17 12:00:00
以前的打孔机不就是这样?
作者: arbwen ( )   2015-08-17 12:00:00
请问一下 常看电影演电话拿起来用个奇怪哨子吹一声再按键那个奇怪哨子吹一下个作用是什么呀?
作者: vn509942 (如履薄冰)   2015-08-17 12:02:00
写程式 程式卡上打洞
作者: ymx3xc (U文多多)   2015-08-17 12:03:00
恩恩恩
作者: cena59473 (感谢小狗)   2015-08-17 12:05:00
推你
作者: locklose (允)   2015-08-17 12:07:00
吹笛子应该是要特殊频率,电话拨号声本身就是用频率控制科南还有一集就是人声拨号这样
作者: philxiao (Sting)   2015-08-17 12:09:00
补充一个有趣的程式语言:Whitespacehttps://zh.wikipedia.org/wiki/Whitespace不是用01写,而更有趣--看起来是一片空白!!但是能跑!!

Links booklink

Contact Us: admin [ a t ] ucptt.com