跳躍逆轉定理
此條目需要精通或熟悉相關主題的編者參與及協助編輯。 (2014年4月23日) |
此條目已列出參考文獻,但因為沒有文內引註而使來源仍然不明。 (2014年4月23日) |
跳躍逆轉定理是遞歸論中關於不可解度的三個定理,定理給出滿足特定條件的不可解度的「圖靈逆跳躍」的存在性。
定理[編輯]
弗里德堡定理[編輯]
設 ,則存在 使 。
肖恩菲爾德定理[編輯]
薩克斯定理[編輯]
設 且可用具備 的預言機遞歸枚舉,則存在遞歸可枚舉集合 使 。
定理[編輯]
參考資料[編輯]
- Rodney G. Downey, Steffen Lempp, and Richard A. Shore. Jumps of Minimal Degress Below (PDF). [2014-04-23] (英語).
- Robert I. Soare. Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets. Springer. 2004. ISBN 9780387152998 (英語).
這是一篇關於數學的小作品。你可以透過編輯或修訂擴充其內容。 |