# 哥德尔机

A Gödel machine is a hypothetical self-improving computer program that solves problems in an optimal way.模板:Clarify It uses a recursive self-improvement protocol in which it rewrites its own code when it can prove the new code provides a better strategy.[1][2] The machine was invented by Jürgen Schmidhuber (first proposed in 2003[3]), but is named after Kurt Gödel who inspired the mathematical theories.[4]

A Gödel machine is a hypothetical self-improving computer program that solves problems in an optimal way. It uses a recursive self-improvement protocol in which it rewrites its own code when it can prove the new code provides a better strategy. The machine was invented by Jürgen Schmidhuber (first proposed in 2003), but is named after Kurt Gödel who inspired the mathematical theories.

The Gödel machine is often discussed when dealing with issues of meta-learning, also known as "learning to learn." Applications include automating human design decisions and transfer of knowledge between multiple related tasks, and may lead to design of more robust and general learning architectures.[5] Though theoretically possible, no full implementation has been created.[6]

The Gödel machine is often discussed when dealing with issues of meta-learning, also known as "learning to learn." Applications include automating human design decisions and transfer of knowledge between multiple related tasks, and may lead to design of more robust and general learning architectures. Though theoretically possible, no full implementation has been created.

The Gödel machine is often compared with Marcus Hutter's AIXItl, another formal specification for an artificial general intelligence. Schmidhuber points out that the Gödel machine could start out by implementing AIXItl as its initial sub-program, and self-modify after it finds proof that another algorithm for its search code will be better.[7]

The Gödel machine is often compared with Marcus Hutter's AIXItl, another formal specification for an artificial general intelligence. Schmidhuber points out that the Gödel machine could start out by implementing AIXItl as its initial sub-program, and self-modify after it finds proof that another algorithm for its search code will be better.

# = 限制 =

Traditional problems solved by a computer only require one input and provide some output. Computers of this sort had their initial algorithm hardwired.[8] This doesn't take into account the dynamic natural environment, and thus was a goal for the Gödel machine to overcome.

Traditional problems solved by a computer only require one input and provide some output. Computers of this sort had their initial algorithm hardwired. This doesn't take into account the dynamic natural environment, and thus was a goal for the Gödel machine to overcome.

The Gödel machine has limitations of its own, however. According to Gödel's First Incompleteness Theorem, any formal system that encompasses arithmetic is either flawed or allows for statements that cannot be proved in the system. Hence even a Gödel machine with unlimited computational resources must ignore those self-improvements whose effectiveness it cannot prove.[3]

The Gödel machine has limitations of its own, however. According to Gödel's First Incompleteness Theorem, any formal system that encompasses arithmetic is either flawed or allows for statements that cannot be proved in the system. Hence even a Gödel machine with unlimited computational resources must ignore those self-improvements whose effectiveness it cannot prove.

# = 感兴趣的变量 =

There are three variables that are particularly useful in the run time of the Gödel machine.[3]

There are three variables that are particularly useful in the run time of the Gödel machine.

• At some time $\displaystyle{ t }$, the variable $\displaystyle{ \text{time} }$ will have the binary equivalent of $\displaystyle{ t }$. This is incremented steadily throughout the run time of the machine.
• At some time t, the variable \text{time} will have the binary equivalent of t. This is incremented steadily throughout the run time of the machine.

• 在某个时刻 t，变量 time 将具有与 t 等价的二进制值。在整个机器的运行时间中，这个值逐步递增。
• Any input meant for the Gödel machine from the natural environment is stored in variable $\displaystyle{ x }$. It is likely the case that $\displaystyle{ x }$ will hold different values for different values of variable $\displaystyle{ \text{time} }$.
• Any input meant for the Gödel machine from the natural environment is stored in variable x. It is likely the case that x will hold different values for different values of variable \text{time}.

• 自然环境中用于哥德尔机器的任何输入都存储在变量 x 中。可能的情况是，对于变量 time 的不同值，x 将持有不同的值。
• The outputs of the Gödel machine are stored in variable $\displaystyle{ y }$, where $\displaystyle{ y(t) }$ would be the output bit-string at some time $\displaystyle{ t }$.
• The outputs of the Gödel machine are stored in variable y, where y(t) would be the output bit-string at some time t.

• 哥德尔机的输出存储在变量 y 中，其中 y (t)是某个时刻的输出位串 t。

At any given time $\displaystyle{ t }$, where $\displaystyle{ (1 \leq t \leq T) }$, the goal is to maximize future success or utility. A typical utility function follows the pattern $\displaystyle{ u(s, \mathrm{Env}) : S \times E \rightarrow \mathbb{R} }$:

At any given time t, where (1 \leq t \leq T), the goal is to maximize future success or utility. A typical utility function follows the pattern u(s, \mathrm{Env}) : S \times E \rightarrow \mathbb{R}:

$\displaystyle{ u(s, \mathrm{Env}) = E_\mu \Bigg[ \sum_{\tau=\text{time}}^T r(\tau) \mid s, \mathrm{Env} \Bigg] }$
u(s, \mathrm{Env}) = E_\mu \Bigg[ \sum_{\tau=\text{time}}^T r(\tau) \mid s, \mathrm{Env} \Bigg]
u (s，mathrm { Env }) = e _ mu Bigg [ sum { tau = text { time } ^ t r (tau) mid s，mathrm { Env } Bigg ]

where $\displaystyle{ r(t) }$ is a real-valued reward input (encoded within $\displaystyle{ s(t) }$) at time $\displaystyle{ t }$, $\displaystyle{ E_\mu [ \cdot \mid \cdot ] }$ denotes the conditional expectation operator with respect to some possibly unknown distribution $\displaystyle{ \mu }$ from a set $\displaystyle{ M }$ of possible distributions ($\displaystyle{ M }$ reflects whatever is known about the possibly probabilistic reactions of the environment), and the above-mentioned $\displaystyle{ \text{time} = \operatorname{time}(s) }$ is a function of state $\displaystyle{ s }$ which uniquely identifies the current cycle.[3] Note that we take into account the possibility of extending the expected lifespan through appropriate actions.[3]

where r(t) is a real-valued reward input (encoded within s(t)) at time t, E_\mu [ \cdot \mid \cdot ] denotes the conditional expectation operator with respect to some possibly unknown distribution \mu from a set M of possible distributions (M reflects whatever is known about the possibly probabilistic reactions of the environment), and the above-mentioned \text{time} = \operatorname{time}(s) is a function of state s which uniquely identifies the current cycle. Note that we take into account the possibility of extending the expected lifespan through appropriate actions.

# = 证明技术使用的指令 =

The nature of the six proof-modifying instructions below makes it impossible to insert an incorrect theorem into proof, thus trivializing proof verification.[3]

The nature of the six proof-modifying instructions below makes it impossible to insert an incorrect theorem into proof, thus trivializing proof verification.

# = = get-axiom (n) =

Appends the n-th axiom as a theorem to the current theorem sequence. Below is the initial axiom scheme:

Appends the n-th axiom as a theorem to the current theorem sequence. Below is the initial axiom scheme:

• Hardware Axioms formally specify how components of the machine could change from one cycle to the next.
• Reward Axioms define the computational cost of hardware instruction and the physical cost of output actions. Related Axioms also define the lifetime of the Gödel machine as scalar quantities representing all rewards/costs.
• Environment Axioms restrict the way new inputs x are produced from the environment, based on previous sequences of inputs y.
• Uncertainty Axioms/String Manipulation Axioms are standard axioms for arithmetic, calculus, probability theory, and string manipulation that allow for the construction of proofs related to future variable values within the Gödel machine.
• Initial State Axioms contain information about how to reconstruct parts or all of the initial state.
• Utility Axioms describe the overall goal in the form of utility function u.
• Hardware Axioms formally specify how components of the machine could change from one cycle to the next.
• Reward Axioms define the computational cost of hardware instruction and the physical cost of output actions. Related Axioms also define the lifetime of the Gödel machine as scalar quantities representing all rewards/costs.
• Environment Axioms restrict the way new inputs x are produced from the environment, based on previous sequences of inputs y.
• Uncertainty Axioms/String Manipulation Axioms are standard axioms for arithmetic, calculus, probability theory, and string manipulation that allow for the construction of proofs related to future variable values within the Gödel machine.
• Initial State Axioms contain information about how to reconstruct parts or all of the initial state.
• Utility Axioms describe the overall goal in the form of utility function u.

• 硬件公理正式指定机器的组件如何从一个周期改变到下一个周期。
• 奖励公理定义硬件指令的计算成本和输出动作的实际成本。相关公理还将哥德尔机的寿命定义为表示所有报酬/成本的标量。
• 环境公理限制了基于先前输入序列 y 从环境中产生新输入 x 的方式。
• 不确定性公理/字符串操作公理是算术、微积分、概率论和字符串操作的标准公理，允许在哥德尔机器中构造与未来变量值相关的证明。
• 初始状态公理包含如何重构部分或全部初始状态的信息。
• 效用公理以效用函数 u 的形式描述总体目标。

# = = apply-rule (k，m，n) =

Takes in the index k of an inference rule (such as Modus tollens, Modus ponens), and attempts to apply it to the two previously proved theorems m and n. The resulting theorem is then added to the proof.

Takes in the index k of an inference rule (such as Modus tollens, Modus ponens), and attempts to apply it to the two previously proved theorems m and n. The resulting theorem is then added to the proof.

# = delete-theorem (m) =

Deletes the theorem stored at index m in the current proof. This helps to mitigate storage constraints caused by redundant and unnecessary theorems. Deleted theorems can no longer be referenced by the above apply-rule function.

Deletes the theorem stored at index m in the current proof. This helps to mitigate storage constraints caused by redundant and unnecessary theorems. Deleted theorems can no longer be referenced by the above apply-rule function.

# = set-switchprog (m，n) =

Replaces switchprog S pm:n, provided it is a non-empty substring of S p.

Replaces switchprog S pm:n, provided it is a non-empty substring of S p.

# = 谢谢观赏 =

Verifies whether the goal of the proof search has been reached. A target theorem states that given the current axiomatized utility function u (Item 1f), the utility of a switch from p to the current switchprog would be higher than the utility of continuing the execution of p (which would keep searching for alternative switchprogs).[3] This is demonstrated in the following description of the decoded check() function for the Gödel Machine:

Verifies whether the goal of the proof search has been reached. A target theorem states that given the current axiomatized utility function u (Item 1f), the utility of a switch from p to the current switchprog would be higher than the utility of continuing the execution of p (which would keep searching for alternative switchprogs). This is demonstrated in the following description of the decoded check() function for the Gödel Machine:

$\displaystyle{ D_{KA} = \frac{ d_\text{pore}} 3 u = \frac{d_\text{pore}} 3 \sqrt{\frac{8\kappa NT}{\pi M_A}} }$
D_{KA} = \frac{ d_\text{pore}} 3 u = \frac{d_\text{pore}} 3 \sqrt{\frac{8\kappa NT}{\pi M_A}}

3 u = frac { d _ text { pore }3 sqrt { kappa NT }{ pi m _ a }

# = = 状态2theorem (m，n) =

Takes in two arguments, m and n, and attempts to convert the contents of Sm:n into a theorem.

Takes in two arguments, m and n, and attempts to convert the contents of Sm:n into a theorem.

# = = 时间有限的 np 难优化 = =

The initial input to the Gödel machine is the representation of a connected graph with a large number of nodes linked by edges of various lengths. Within given time T it should find a cyclic path connecting all nodes. The only real-valued reward will occur at time T. It equals 1 divided by the length of the best path found so far (0 if none was found). There are no other inputs. The by-product of maximizing expected reward is to find the shortest path findable within the limited time, given the initial bias.[3]

The initial input to the Gödel machine is the representation of a connected graph with a large number of nodes linked by edges of various lengths. Within given time T it should find a cyclic path connecting all nodes. The only real-valued reward will occur at time T. It equals 1 divided by the length of the best path found so far (0 if none was found). There are no other inputs. The by-product of maximizing expected reward is to find the shortest path findable within the limited time, given the initial bias.

# = = 快速定理证明 = =

Prove or disprove as quickly as possible that all even integer > 2 are the sum of two primes (Goldbach’s conjecture). The reward is 1/t, where t is the time required to produce and verify the first such proof.[9]

Prove or disprove as quickly as possible that all even integer > 2 are the sum of two primes (Goldbach’s conjecture). The reward is 1/t, where t is the time required to produce and verify the first such proof.

# = = 用有界资源最大化期望报酬 = =

A cognitive robot that needs at least 1 liter of gasoline per hour interacts with a partially unknown environment, trying to find hidden, limited gasoline depots to occasionally refuel its tank. It is rewarded in proportion to its lifetime, and dies after at most 100 years or as soon as its tank is empty or it falls off a cliff, and so on. The probabilistic environmental reactions are initially unknown but assumed to be sampled from the axiomatized Speed Prior, according to which hard-to-compute environmental reactions are unlikely. This permits a computable strategy for making near-optimal predictions. One by-product of maximizing expected reward is to maximize expected lifetime.[3]

A cognitive robot that needs at least 1 liter of gasoline per hour interacts with a partially unknown environment, trying to find hidden, limited gasoline depots to occasionally refuel its tank. It is rewarded in proportion to its lifetime, and dies after at most 100 years or as soon as its tank is empty or it falls off a cliff, and so on. The probabilistic environmental reactions are initially unknown but assumed to be sampled from the axiomatized Speed Prior, according to which hard-to-compute environmental reactions are unlikely. This permits a computable strategy for making near-optimal predictions. One by-product of maximizing expected reward is to maximize expected lifetime.

Gödel's incompleteness theorems

= = 也见

• 哥德尔的不完备性定理

## References

1. Mahmud, M. M. Hassan (2008). Universal Transfer Learning. pp. 16–18. ISBN 9780549909880.
2. Anderson, Michael L.; Tim Oates (Spring 2007). "A review of recent research in metareasoning and metalearning". AI Magazine. 28 (1): 7.
3. Schmidhuber, Jürgen (December 2006). Gödel Machines: Self-Referential ¨ Universal Problem Solvers Making Provably Optimal Self-Improvements. Retrieved 10 November 2014.
4. Schaul, Tom; Schmidhuber, Juergen (2010). "Metalearning". Scholarpedia. 5 (6): 4650. Bibcode:2010SchpJ...5.4650S. doi:10.4249/scholarpedia.4650. Retrieved 10 November 2014.
5. Steunebrink, Bas R.; Schmidhuber, Jürgen (2011). A Family of Gödel Machine Implementations. 6830. pp. 275–280. doi:10.1007/978-3-642-22887-2_29. ISBN 978-3-642-22886-5.
6. Schmidhuber, Jürgen (5 March 2009). "Ultimate Cognition à la Gödel" (PDF). Cognitive Computation. 1 (2): 177–193. CiteSeerX 10.1.1.218.3323. doi:10.1007/s12559-009-9014-y. Retrieved 13 November 2014.
7. Schmidhuber, Jürgen (5 March 2009). "Ultimate Cognition à la Gödel" (PDF). Cognitive Computation. 1 (2): 177–193. CiteSeerX 10.1.1.218.3323. doi:10.1007/s12559-009-9014-y. Retrieved 13 November 2014.
8. Schmidhuber, Jürgen (5 March 2009). "Ultimate Cognition à la Gödel". Cognitive Computation. 1 (2): 177–193. CiteSeerX 10.1.1.218.3323. doi:10.1007/s12559-009-9014-y.