iT邦幫忙

2024 iThome 鐵人賽

DAY 23
0
Software Development

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

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

  • 分享至 

  • xImage
  •  

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

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

圖靈完備

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

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

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

就圖靈完備了。

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

以 C 語言為例

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

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

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

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


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

尚未有邦友留言

立即登入留言