數理論理學 및 컴퓨터 科學 에서 μ-再歸 函數 ( 英語 : μ-recursive function ) 또는 簡單히 再歸 函數 란, 自然數 에서 自然水路의 '計算可能한' 部分 函數 이다. 再歸 理論 에서는, μ-再歸 函數와 튜링 機械 로 計算可能한 函數가 一致하는 것임이 알려져 있다. 有名한 例로 피보나치 수 等이 있다.

μ-再歸 函數는 遠視 再歸 函數 와 密接한 關聯이 있으며, 그 再歸的(歸納的) 正義가 遠視 再歸 函數에 기초하고 있다. 다만, μ再歸函數가 모두 遠視 再歸 函數인 것은 아닌데, 그러한 例로 아커만 函數 等이 있다.

또 再歸函數와 一致하는 槪念으로는, 람다 計算 에서 쓰이는 再歸函數나 마르코프 알고리즘 (Markov algorithms)으로 計算可能한 函數 等이 있다.

轉役 μ-再歸 函數를 모은 클래스는 複雜度 클래스 R 과 같다. 이는 PR 을 包含한다.

正義 [ 編輯 ]

μ-再歸 함수란, 有限 個의 自然數의 튜플을 醉하여 1個의 自然水를 내어놓는 部分 函數를 가리키는 말로, 이들의 클래스는 初等函數를 包含하면서 合成, 遠視再歸, μ作用素(μ演算子)에 對하여 닫혀 있는 部分 函數 의 클래스 中 最少의 것이다.

遠視 再歸 函數 와 똑같은 方式으로 定義되지만, 轉役 函數이며 μ 演算子가 追加되어 있다는 點에서 다르다. 때문에 아커만 函數 와 같이 遠視 再歸 函數는 아니면서 轉役 再歸 函數인 것을 定義에 包含할 수 있다. μ-再歸函數에서 μ 演算子는 比喩界 (unbounded)의 '探索' 作用素로서 作用하며, 마지막으로 수를 내어놓고 演算을 終了시키는 役割을 한다.

그러나, 萬若 比喩界 μ 作用素 그 自身이 部分的이라면(즉 수를 내어놓지 못하는 境遇가 存在한다면) 그것이 쓰인 函數 亦是 部分函數가 되어 一部 數에 對하여 定義되지 않게 된다. 이러한 境遇, μ作用素는 比喩系이기 때문에 探索을 끝없이 繼續할 것이고, 結局 永遠히 수를 내어놓고 計算을 終了하지 못하게 된다. (間或 非決定임을 나타내는 記號 u를 내어놓을 수 있고 演算을 끝내도록 定義해두기도 한다.) 다르게 말하면, 部分 μ作用素를 쓰는 部分 μ再歸 函數는 全域的이지 않을 수도 있다.

初等函數 [ 編輯 ]

于先 다음을 初等函數로 定義한다(Kleene (1952) p. 219 에 根據):

1. 常數 函數 (constant function): 各 自然數 ${\displaystyle n}$과 ${\displaystyle k}$에 對하여:

   ${\displaystyle f(x_{1},\ldots ,x_{k})=n}$.

   精髓 ${\displaystyle n}$은, 0萬을 내어놓는 英函數에 따름數 函數의 合成을 反復시키는 것으로서 定義하기도 한다.

2. 따름數 函數 (successor function) S :

   ${\displaystyle S(x){\stackrel {\mathrm {def} }{=}}f(x)=x'=x+1\,}$

3. 私營 函數 (projection function) ${\displaystyle P_{i}^{k}}$: ${\displaystyle 1}$ ≤ ${\displaystyle i}$ ≤ ${\displaystyle k}$를 滿足하는 모든 自然數 ${\displaystyle i,k\,}$에 對하여:

   ${\displaystyle P_{i}^{k}(x_{1},\ldots ,x_{k}){\stackrel {\mathrm {def} }{=}}f(x_{1},\ldots ,x_{k})=x_{i}}$

作用素 [ 編輯 ]

다음은 作用素(演算子)이다:

1. 合成 作用素 (composition operator): m港 函數 ${\displaystyle h(x_{1},\ldots ,x_{m})\,}$와 m個의 k港 函數 ${\displaystyle g_{1}(x_{1},\ldots ,x_{k}),\ldots ,g_{m}(x_{1},\ldots ,x_{k})}$를 取하여, ${\displaystyle x_{1},\ldots ,x_{k}}$를 다음과 같이 매핑하는 函數를 反復하는 造作이다:

   ${\displaystyle f(x_{1},\ldots ,x_{k})=h(g_{1}(x_{1},\ldots ,x_{k}),\ldots ,g_{m}(x_{1},\ldots ,x_{k}))}$

2. 遠視 再歸 作用素 (primitive recursion operator): 函數 ${\displaystyle g(x_{1},\ldots ,x_{k})}$와 ${\displaystyle h(y,z,x_{1},\ldots ,x_{k})}$를 取하여 다음과 같은 函數 ${\displaystyle f}$를 反復하는 造作이다:

   ${\displaystyle f(0,x_{1},\ldots ,x_{k})=g(x_{1},\ldots ,x_{k})}$,

   ${\displaystyle f(y+1,x_{1},\ldots ,x_{k})=h(y,f(y,x_{1},\ldots ,x_{k}),x_{1},\ldots ,x_{k})}$.

3. μ 作用素 : 函數 ${\displaystyle f(y,x_{1},\ldots ,x_{k})}$를 取하여, ${\displaystyle x_{1},\ldots ,x_{k}}$를 變數로 하는 函數 ${\displaystyle \mu yf(y,x_{1},\ldots ,x_{k})}$를 反復하는 造作이다. 여기서 函數 ${\displaystyle f}$는 自然數 ${\displaystyle \{0,1,...n\}}$로부터 自然數 ${\displaystyle \{0,1,...n\}}$로의 數論的 函數이거나 値域이 ${\displaystyle \{0,1\}}$人 眞理값을 나타내는 指示函數 이다. 또 函數 ${\displaystyle \mu yf}$는 ${\displaystyle f(0,x_{1},\ldots ,x_{k}),f(1,x_{1},\ldots ,x_{k}),...,f(y,x_{1},\ldots ,x_{k})}$가 모두 結果값을 내어놓을 때 ${\displaystyle f(y,x_{1},\ldots ,x_{k})=0}$를 만족시키는 自然數 ${\displaystyle y}$가 存在하면 그 中 最少의 값을 내어놓고, 萬若 그러한 ${\displaystyle y}$가 없으면 ${\displaystyle \mu yf}$는 變數 ${\displaystyle x_{1},\ldots ,x_{k}}$에 對하여서는 定義되지 않는다.

計算可能性 理論에서 [ 編輯 ]

(halt하지 않을 可能性을 가지는) 튜링 機械 의 計算能力과 一致하며, 處置-튜링 命題 는 "μ-再歸에 該當한다는 것이 '計算可能'이라는 無定義 用語에 對한 最適의 定義"이라는 主張이다.

원시재귀와의 關係 [ 編輯 ]

μ 演算子는 一部 入力값에 對하여 定義되지 않을 수 있으며, 컴퓨터的으로 表現하면 計算이 끝나지 않고 永遠히 繼續될 수 있다. 이로 인해 遠視 再歸와의 決定的 差異가 發生하지만, 클레이니의 정규형 定理에 依하면 모든 再歸函數는 遠視再歸函數와 μ 演算子를 結合한 形態로 適切히 分解할 수 있다.

같이 보기 [ 編輯 ]

• 計算 可能性 理論
• 遠視 再歸 函數
• 計算 可能 函數