完全只用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,但真的可以拿来写程式吗?