iT邦幫忙

2024 iThome 鐵人賽

DAY 23
0
Software Development

離塵指引.卷之一.試結丹:程式語言自舉系列 第 23

音界咒零.二版設計(上)圖靈完備

  • 分享至 

  • xImage
  •  

零.一版是沒法自舉的,它甚至難以稱之為「咒」。「咒」必須圖靈完備,圖靈完備之後,才有條件自舉。

在零.二版,貧道將嘗試定義一極度簡單但圖靈完備的法咒。

圖靈完備

圖靈機有一套嚴謹的符號定義,但貧道不打算在此細述,首先,雖然當代電腦/通用法咒(程式語言)都圖靈完備,但這套原始的符號定義與現今的計算機/法咒有不小的差異,需要一些推導才能證明兩者是等價的。

基本上,首先想像有一個「咒指針」指向法咒正在執行的行數,法咒只要有語句能控制

  • 循序,即咒會一行一行往下執行(咒指針遞增)
  • 修改記憶體狀態
  • 決策,可根據「條件」決定咒指針要跳躍至何處
    • 這個「條件」是「當下記憶體狀態」的函數

就圖靈完備了。

編譯器生成真言後,放到真實機器上本就會逐步執行,因此循序不會是問題,只要檢視後兩條即可

以 C 語言為例

  • 賦值語句能修改記憶體狀態
  • if 搭配 goto 能根據條件選擇性跳躍到任意一行

決策有很多種實現,if 必不可少,用 if 搭配 goto 當然是最直觀符合定義的,但 while 也能取代 goto ,可證明 whilegoto 的能力等價。思路是嘗試找到一種方法把 while 轉換為 goto ,同時找到一套方法把 goto 轉換為 while

除了 gotowhile ,遞迴也是一種與 if 搭配來達到圖靈完備的方法。道友可嘗試將 while 與遞迴互相轉化來證明。

而多數流行的法咒會同時提供 while 與遞迴,乃至迭代器、for 迴圈等等語句,什麼好寫就支援什麼。


上一篇
雜項:精五(RISC-V)組語除錯器介紹
下一篇
音界咒零.二版設計(下)引入「術」、「若」語句
系列文
離塵指引.卷之一.試結丹:程式語言自舉31
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言