圖靈電子與電氣工程叢書(shū):開(kāi)關(guān)電源手冊(cè)

《圖靈電子與電氣工程叢書(shū):開(kāi)關(guān)電源手冊(cè)(第3版)》適用于開(kāi)關(guān)電源的專業(yè)設(shè)計(jì)人員和研究人員，也適用于電類學(xué)生、初級(jí)工程師和感興趣的非專業(yè)人士。

作者:(美)Billings

可以通過(guò)只有兩個(gè)計(jì)數(shù)器的機(jī)器模擬任何圖靈機(jī)。下面用三個(gè)步驟概述其證明。首先，圖靈機(jī)可以用裝備了兩個(gè)棧的有限狀態(tài)機(jī)(FSM)來(lái)模擬。接著，兩個(gè)?？梢杂盟膫€(gè)計(jì)數(shù)器模擬。最后，四個(gè)計(jì)數(shù)器可以用兩個(gè)計(jì)數(shù)器模擬。

圖靈機(jī)由一個(gè) FSM 和一個(gè)最初填充零的無(wú)限磁帶組成，機(jī)器可以在其上寫一和零。在任何時(shí)候，這個(gè)機(jī)器的讀/寫磁頭指向在磁帶上的一個(gè)單元。這個(gè)磁頭概念上在這一點(diǎn)上把磁帶分為兩每一半磁帶都可以被當(dāng)作棧，棧頂是最靠近讀/寫磁頭的單元，而棧底與磁頭有些距離，而在磁帶上的所有零都超出了棧底。因此圖靈機(jī)可以用 FSM 加上兩個(gè)棧來(lái)模擬。左或右移動(dòng)磁頭等價(jià)于從一個(gè)棧彈出一位并壓入到另一個(gè)棧中。寫等價(jià)于在壓入一位之前改變它。

包含零和一的?？梢杂脙蓚€(gè)計(jì)數(shù)器模擬，當(dāng)在棧上的位被認(rèn)為表示二進(jìn)制數(shù)的時(shí)候，而棧頂是最低位。壓入零到棧頂?shù)葍r(jià)于雙倍這個(gè)數(shù)。壓入一到棧頂?shù)葍r(jià)于雙倍并加 1。彈出等價(jià)于除以 2，這里的余數(shù)是彈出的位。兩個(gè)計(jì)數(shù)器可以模擬一個(gè)棧，一個(gè)計(jì)數(shù)器持有其二進(jìn)制表示表示在棧上的位的數(shù)，而另一個(gè)計(jì)數(shù)器用做暫存器。要雙倍在第一個(gè)寄存器內(nèi)的數(shù)，F(xiàn)SM 可以初始化第二個(gè)計(jì)數(shù)器為零，接著重復(fù)減少第一計(jì)數(shù)器一次而增加第二個(gè)計(jì)數(shù)器兩次。繼續(xù)直到第一個(gè)寄存器到達(dá)零。在這一點(diǎn)上，第二個(gè)寄存器將持有雙倍的這個(gè)數(shù)。減半通過(guò)減少一個(gè)計(jì)數(shù)器兩次而增加另一個(gè)一次，重復(fù)知道第一個(gè)計(jì)數(shù)器到達(dá)零來(lái)實(shí)現(xiàn)。余數(shù)可以通過(guò)它在偶數(shù)或奇數(shù)次嘗試后結(jié)束來(lái)確定。

同上，一個(gè)計(jì)數(shù)器用做暫存器。另一個(gè)真實(shí)計(jì)數(shù)器持有一個(gè)整數(shù)，它的素因數(shù)分解是 2a3b5c7d。指數(shù) a, b, c 和 d 可被看作要被模擬的四個(gè)虛擬計(jì)數(shù)器。如果真實(shí)計(jì)數(shù)器被置零接著增加一次，則等價(jià)于把所有寄存器都置零。如果真實(shí)計(jì)數(shù)器被雙倍，則等價(jià)于增加 a，而如果它被減半，則等價(jià)于減少 a。通過(guò)類似的過(guò)程，它可以乘以或除以 3，這等價(jià)于增加或減少 b。類似的，c 和 d 可以增加或減少。要檢查一個(gè)虛擬計(jì)數(shù)器比如 c 是否等于零，只要把實(shí)際計(jì)數(shù)器除以 5，看余數(shù)是什么，接著乘以 5 并加回余數(shù)。這保持真實(shí)計(jì)數(shù)器不變。余數(shù)將是非零當(dāng)且僅當(dāng) c 是零。

作為結(jié)果，帶有兩個(gè)計(jì)數(shù)器的 FSM 可以模擬四個(gè)計(jì)數(shù)器，依次模擬兩個(gè)棧，再次模擬圖靈機(jī)。所以，F(xiàn)SM 加上兩個(gè)計(jì)數(shù)器至少有圖靈機(jī)一樣的能力。圖靈機(jī)可以輕易的模擬帶有兩個(gè)計(jì)數(shù)器的 FSM，所以兩個(gè)機(jī)器有等價(jià)的能力。