轉換器（transducer）

目前為止，圖靈機一直是個法官，回答是或非。但機器也可以是個計算器：拿一些輸入、產生一些輸出。轉換器（transducer）就是這樣使用的圖靈機，用來計算一個「函數」，而非判定成員。你問的不是「這字串在語言中嗎？」，而是「這字串會變成什麼？」。想像一台投幣後吐出特定零食、而不只是給出是或非的販賣機。

具體來說，轉換器一開始把輸入寫在紙帶上、運行，當它停機時，紙帶上留下的內容（依固定約定讀取，例如從讀寫頭結束處開始的非空白字串）就是輸出。我們說機器計算函數 f，若對任何輸入 w 起始，它都以紙帶上的 f(w) 停機。要讓這定義出真正的函數，機器必須對每個輸入都停機，就像判定器一樣，好讓輸出永遠有定義。一個簡單例子：讀入一個二進位數、寫回該數加一（二進位遞增）的轉換器，或一台把輸入複製成 ww 的轉換器。

轉換器之所以重要，是因為它顯示圖靈機是完整意義下的計算模型，而不只是語言的接受器。每一種可計算函數的概念（把數相加、排序一個串列、編譯一個程式）都能寫成一個轉換器。事實上判定一個語言只是特例：判定器是輸出只有接受或拒絕兩個值之一的轉換器。邱奇-圖靈論題（可計算函數恰好是圖靈可計算者）其實是關於轉換器能做什麼的一個論述。