数学论文（无限时间图灵机） (6-6)

在联合工作[HMW07]中，我们定义了一个模型a=hA。i是无限时间可计算的，如果A⊆R是可判定的，并且所有函数、关系和常数都是一致的无限时间，可根据其G模型代码和输入进行计算。结构A是可判定的，如果可以计算出A|=[¯一]给定pΓq和¯一理论T是无限时间可判定的，如果关系T⊢Γ在pΓq中是可计算的。因为我们想处理不可计数的语言，G模型代码的自然上下文是R而不是N。

当然，最初的问题是完全性定理的无限时间可计算模拟：每个一致的可判定理论都有一个可判定模型吗？这个这个答案和ZFC无关。

定理4（[HMSW07]）。完全性定理的无限时间可计算模拟独立于ZFC。明确地：

（1） 如果V=L，那么每个一致的无限时间可判定理论都有一个无限时间可决定模型，在语言的可计算翻译中。

（2） 与ZFC相对一致的是，在可计算呈现的语言，在中没有无限时间的可计算或可判定模型该语言的任何翻译。

（1）的证明使用了表示良好的语言L的概念，对于该语言存在符号hsα|α＜δi的枚举使得从任何psαq可以一致计算先验符号hpsβq|β≤αi的代码。可以证明每一个一致的在一个表现良好的语言中的可判定理论有一个可判定模型，如果V=L，那么每一种可计算语言都有一个表现良好的可计算翻译。对于（2），一使用理论T扩展了hWO，lect i的原子图，同时断言f是select类上的选择函数。这是一个可判定的理论，但对于任何可计算的模型A=hA，lect，fi的T，集{f（cu）|u∈WO}为∑1.2.并且具有基数ω1。众所周知与ZFC一致，即没有∑1.2.集合的大小为ω1。

对于L¨owenheim-Skolem定理的无限时间类似物，我们证明了每一个充分呈现的无限时间可判定模型都有一个适当的向上版本具有可判定表示的初等扩展，对于向下的版本，每个充分表示的不可数可判定模型都有一个可数可判初等下部结构。的完全直接推广有很强的反例。

然而，L¨owenheim-Skolem定理，因为[HMW07]在整个实数集上提供了一个可计算结构hR，Ui，它没有合适的可计算初等子结构。

一些最有趣的工作涉及可计算商。结构具有无限时间可计算表示，如果它同构于可计算结构，以及具有可计算商表示，如果它同构于可计算的商结构通过可计算的等价关系（同余）。对于N上的结构，在无论是在有限的还是无限的时间背景下，这些概念都是等价的，因为人们可以可计算地找到任何等价类的最小元素。然而对于R上的结构，计算每个等价类的这种可区分元素并不总是可能的。

数学联邦政治世界观提示您：看后求收藏（同人小说网http://tongren.me），接着再看更方便。