halting problem的oracle可以计算出所有的函数吗？不能。
如果仅仅是图灵机停机函数的 Oracle 是无法计算所有的满足
的函数的。原则上：一个很简单的原因是通过简单的对角化论证可以在原有的 Oracle 下构造这个 Oracle 无法计算的停机问题。
但是呢，如果题主不追求那么强大的条件，把其中的条件稍微弱化一下：“给定一个对于 halting problem 的 oracle
给配了这一 oracle 的图灵机称之为
那么这个
可以计算的函数可以走多远？”
一般的回答是：位于
不能再多了。
但有的学者给出了其他的可能性！！
问题是：当图灵机
配备了一个 oracle，并用同样的 oracle 对
的停机问题进行编码时，会发生什么。
当然，在这种形式下，问题是极其显然的：
的停机问题是无法解决的。但是，仍然可以尝试看看在不遇到矛盾的情况下可以走多远！一个可能是：一个
可能会对不调用 oracle 的程序的停机行为进行编码。它还可以对自身调用 oracle 之程序的停机行为 / halting behavior 进行编码，以了解不调用 oracle 的程序的停机行为。重复这个想法，就会得到
的概念，它具有更强的超计算性。这是极其惊人的。
这样一台机器
的可计算集合将位于
- sets。
具体工作：
Feedback Turing Computability, and Turing Computability as Feedback（个人而言）这项工作意义非凡：假如未来我们真的能够找到物理可实现且具有可操作性的
的话，但是这个
在原则上仅仅能够解决图灵机的停机问题的话。为了达到最大化的计算能力的潜在操作措施。而不仅仅是停留在不可解度的最底层。
附录：对于函数
我们称
可以被
至
写作

定义一个
：
的
将作为对包含某些整数
之序数进行赋值（与
相关） 的 ordinal notations （写作
）之 domain。

若
那么有
若存在一个
使得
是一个全函数 / total function 进一步对于每一个
其表示

来源：(未知)

【】网址：http://www.shadafang.com/c/gx04219A5092020.html

标题：halting problem的oracle可以计算出所有的函数吗