但是看來還有一個“合理的計算模型”這一概念有關的論題。和對這一概念作了下列的論述：
“迄今為止研究過的計算機的現實模型，如單帶機、多帶丁以機、任意存取機相對於多項式複雜性都是等價的。我們將期望任何其它合理的模型都是等價的。此處合理的這一概念是說，存個單位時間中所能完成的計算工作量存在多項式。例如具有能夠執行任意多次操作的能力的計算模型就是不合理的。已有的或計劃中的計算機都不具有這種能力。無論如何，隻要我們限於討論現實計算機的標準型，難，原稿為英文，郭世銘譯解問題的類將不受所用計算模型是哪一種的影響。我們將以是否便利為標準來選定計算模型，而不犧牲我們的結果的可應用性。”
上麵這段話澄清了可行性概念和“合理的模型”概念之間的相互關係。下麵我們將論證：大致等價性論題可以從合理性模型論題推出，而問題是和這兩個論題都有關係的。
所說的計算模型是指理想計算機，任意存取機等等，所說的大致等價性如前所述是指相對於多項式複雜性的等價性。兩個模型間的等價性可定義如下：
計算模型和是大致等價的，當且僅當和12能在多項式時間和多項式空間內互相模擬。近年曾指出，就已有的計算模型而言一個對另一個的模型最多隻相差平方數即如果在第一種模型中，複雜性為在第二種模型中複雜性最多為係就計算時間而言，其他人將此結果推廣到存貯空間。在文獻中已提出了稱為“大致等價性論題”的下列命題：
一切合理的計算模型就計算時間和存貯空間而言都是彼此大致等價的。
容易看出，如果大致等價性係指兩個計算時間在多項式時間和多項式空間之內能彼此模擬，而合理的計算模型係指那些能夠在多項式時間和多項式空間之內與彼此互相模擬的計算模型，則上述論題可立即推出。
模型論和計算複雜性(詳細摘要）
普遍認為，下界問題是計算複雜性理論的一個核心問題。因此，近年來在一類問題的非多項式下界的存在與“皮亞諾算術”算術的一個片段的非標準模型的存在性之間的相互關係之間所作的發現就十分令人感興趣。1979年證明：一個給定的問題類有非多項式的下界，當且僅當“皮亞諾算術”的某個片段有非標準模型。他指出，這個結果為人們在證明下界存在性時遇到的困難做出了解釋。上述的結果明確地揭示了模型論與計算雜性理論之間的密切關係。
在數理邏輯近年的進展中，積極的研究結果證明算術中的一個自然的不可判定命題的獨立性本身就引起了人們的極大興趣。除此之外，由於人們早已猜測計算複雜性理論中的某些未解決的問題是在“皮亞諾算術”中不可判定的，他們的技巧就與計算複雜性有關了。
完備性定理的一個新的證明：證明一個能夠解釋為斷言“皮亞諾算術”的可靠性在“皮亞諾原稿為英文，郭世銘譯。算術”中不可證的博弈論命題。他的證明是個模型論證明，其思想可以簡述如下：
有可能定義一種與某些邏輯概念（大體上就是“可滿足性”的概念）有關的博弈，並構造一個算術命題，它斷言第二名博弈者有必勝策略。使用模型論的技巧證明這個命題在“皮亞諾算術”中的不可判定性是可證的。具體地說，是證明該命題在標準模型中成立但在非標準模型中不成立，從而就證明了它在“皮亞諾算術”中不可判定。
上麵說過，人們早已猜測某些未解決的問題在算術中不可判定，而且我們又知道對角線方法不能用來證明？(如果它們真的相等），因此，看起來模型論方法就有可能是合用的了。
此外，關於一個問題類的非多項式下界的存在性問題，能夠歸約為關於“皮亞諾算術”的某個片段的非標準模型的存在性問題。因而，期望？等價於“皮亞諾算術”的某個特定的片段有非標準模型這個命題在“皮亞諾算術”中不可判定就是合乎情理的了。這件事或許可以通過證明下述命題而獲得成功：
“皮亞諾算術”有非標準模型這一斷言在標準模型中成立而在非標準模型中不成立。