波斯特问题【英】

Post’s problem

译文来源

金炳华，冯契.哲学大辞典[Z].上海辞书出版社，2001：104.

定义

“美国逻辑学家波斯特于1944年提出的关于不可解度问题，即在递归T度O和含K集的递归可枚举T度O′间，是否存在不同于它们的递归可枚举T度a？递归T度是指含有一个递归集的任意T度。递归可枚举T度则是指含有一个递归可枚举集的任意T度，简记作r．e．T度。集合K={n|Tn（n）停机}，是递归可枚举的非递归集。所有递归集组成惟一的一个递归T度，记作O。它是惟一的最小度。令O′为含集合K的r．e．T度，它是所有r．e．T度中最大的。显然，O﹤O′。波斯特问题也可以这样叙述：是否存在一个r．e．T度a，使得O﹤a﹤O′？直到1956年，由弗列特伯格（Friedberg）和摩契尼克（Мучник）解决了这一问题。他们的结论是：存在两个递归可枚举但非递归的集A，B，使得A≰TB与B≰TA（这时称A与B是不可比较的）。于是，令a=dT（A）（即含有A的T度），b=dT（B）（即含有B的T度），则有O

定义来源

[1] 金炳华，冯契.哲学大辞典[Z].上海辞书出版社，2001.
[2] “10000个科学难题”数学编委会.10000个科学难题（数学卷）[Z].科学出版社，2009.

网络参考例句

例句 1：
即使我们撇开殖民统治就其事实本身而言是否就是不正义的这一问题，我认为对波斯特问题的回答是肯定的。——“全球正义问题”，载于《吉首大学学报（社会科学版）》2010年第6期

例句 2：
本文以马克·波斯特划分的两个媒介时代为时间轴来分析场域传播在不同媒介时代的传播方式，场域传播作为做基本的传播方式在大众传播技术的解构与重建中几经变迁。——《场域传播在当代传播技术下的解构与重建》，吉林大学硕士学位论文，2013
Mark Post divided the two media age timeline to analyze the field propagation mode of transmission in different media era, Field propagation as the basic mode of transmission to several changes in media technology deconstruction and reconstruction.