社会性软件：关于知识和行动的研究

49网址：http://www.elsevier.nl/locate/entcs/volume67.html12页State ofKnowledgeRohitParikh2;1计算机科学系研究生中心纽约城市大学第五大道纽约，纽约州，10016-4309美国摘要当一群人在思考某个真正的公式A时，他们中的一个人可能知道它，他们中的所有人可能都知道它，或者它可能是常识。但也有许多其他可能的知识状态，当交流发生时，它们会发生变化。什么样的知识状态是可能的？这种变化的动力是什么？他们如何采取可能的协调行动？我们描述了在这一领域的一些发展。关键词：知识，知识状态，社会性软件，分布式知识一个旅行推销员发现自己和妻子在家里过夜，因为他的一次旅行意外取消了。他们两个都睡得很熟，半夜里有人大声敲门。前门妻子被惊醒了，叫道：“哦，我的上帝！是我丈夫！”于是丈夫从床上跳了起来，穿过房间，跳出窗户。Schank and Abelson，1977，p. 59.1引言Wimmer和Perner以Schank和Abelson的这个故事开始了他们关于信念的信念的论文[19]，这个故事可能对一些人来说很有趣，对另一些人来说很混乱。但故事的重点似乎是，丈夫和妻子都有自己的场景，都不符合现实。1 电子邮件地址：rparikh@gc.cuny.edu2 由NSF和CUNY-FRAP计划资助的研究2002年由ElsevierScienceB. V. 操作访问根据C CB Y-NC-N D许可证进行。50维默和佩纳本人主要关注的是儿童对他人心态的理解。下面引用[19]是一个关于马克西的故事（奥地利英语），他们告诉一群孩子：妈妈购物回来了。她买了巧克力做蛋糕。马克西可能会帮她收拾东西。他问她：“我应该把巧克力放在哪里？”“在蓝色的碗橱里，”母亲说。后来，马克西出去玩了，妈妈把巧克力从蓝色的橱柜转移到绿色的橱柜里。马克西从操场回来，饿了，他想买些巧克力。在Wimmer和Perner的实验中，被告知Maxi故事的孩子们被问到了“信念”问题：“Maxi会在哪里找到巧克力？”“3岁或3岁以下的孩子总是答错，并认为马克西会在他们知道的绿色橱柜里找巧克力。即使是4-5岁的孩子也只有三分之一的机会正确回答这个问题或一个涉及马克西和他的兄弟（谁也想要巧克力，马克西想欺骗谁）的类比问题。相比之下，6岁或6岁以上的孩子很成功地意识到马克西会认为巧克力会在蓝色的橱柜里，如果他想欺骗他的兄弟，他应该把他的兄弟带到绿色的橱柜里。因此，对他人心态的表征似乎在童年时期相当晚才出现，在他们学会为自己和分享自己现实观点的他人处理信仰和基于信仰的行动的概念之后。在[18]克里斯Steinsvold调查模态逻辑，旨在代表幼儿的心理状态。见[17]。大一点的孩子也好不到哪里去在我女儿七年级的一次实验中，我发现他们无法处理超过最初一两个级别的泥泞儿童拼图。在这个现在众所周知的谜题中，一些孩子在泥里玩耍，其中一些人把额头弄脏了。这时，父亲出现了，并宣布：“你们中至少有一个人把额头弄脏了。”场景1：假设只有一个孩子，比如说艾米，他很脏。然后她会意识到，她自己的额头一定是脏的，因为她可以看到别人是干净的。场景2：假设现在有两个脏兮兮的孩子，莎拉和艾米，他们被依次问到：“你知道你的额头是否脏吗？”“现在，当莎拉被问到这个问题时，她可以看到艾米肮脏的额头，她回答说，‘我不知道’。然而，当艾米被问到这个问题时，她能够推理，“如果我的前额是干净的，莎拉就会知道她的前额一定是脏的，因为其他的前额都是干净的。但莎拉不知道。所以我的额头一定很脏。“艾米的这一推理要求艾米代表莎拉的精神状态，显然艾米必须至少六岁才能起作用。然而，在这方面，51莎拉自己必须有一定的推理能力，艾米必须知道她有这样的能力。艾米知道莎拉对现实的看法是不够的，她还必须在自己的头脑中代表莎拉的逻辑能力随着脏孩子的数量增加，需要越来越高水平的“我知道他知道她知道......“.常识是在这条路的尽头，并已被用来解释协调行为（[8，6，2]）。例如，Halpern和Moses在[6]中指出，协同攻击问题需要两个将军之间的共同知识，而考虑到他们拥有的通信手段，这种共同知识是不可能获得的。克拉克和马歇尔指出了类似的困难与“电影播放的罗克西今天”的指涉。虽然协调的行动和所谓的共同知识确实会发生，但考虑其他知识水平也可能是相关的，除了即时的共同知识水平。3 这种水平也出现在某些实用的情况下，例如，电子邮件或蜗牛邮件或电话留言作为语音邮件。因此，本文的目的是研究水平除了常识。在典型的合作情况下，即使需要一定的知识水平，更高的水平也可以。如果鲍勃想让吉尔在下午4点去接孩子，他只要知道吉尔知道就够了。所以如果他派在这种情况下，鲍勃知道安会及时知道孩子们的情况，或者从政治上讲，知道安会及时知道孩子们的情况，他可能会觉得这就足够了。 然而，如果他在下午3点打电话给她，这将创造一个共同的知识，C、比需要的多。 但这并没有造成什么伤害，因为在这种情况下，安和鲍勃有着相同的目标。Halpern和Zuck还指出了序列传输问题的知识水平要求，这是最低限度的，但由于各方正在协调，更高的水平不会造成伤害。但在其他情况下，人们可能只希望有一个特定的知识水平，不低，也不高。例如，假设鲍勃想让安知道他正在做的一个研讨会演讲，以防万一她想来，但他不想让她感到有压力去参加（她应该只是出于兴趣而不是出于礼貌）。在这种情况下，他将不会安排Kb（Ka（S）），（他自己知道她在研讨会上知道了ab），而不是Ka（Kb（Ka（S）3 下面这个关于数学家诺伯特·维纳（Norbert Wiener）的故事（可能是杜撰的）说明了一些更微妙的东西。维纳以心不在焉而闻名有一段时间，维纳一家正在搬家，早上他去上班时，夫人。维纳对他说：“现在晚上不要回到这个地址。“她给了他一张写有新地址的纸然而，到了晚上，维纳发现自己站在旧地址前，不知道该怎么办（他同时丢失了写有新地址的纸条。他走到一个站在旁边的小女孩面前说：“小女孩，你知道香肠一家搬到哪里去了吗小女孩回答说：“爸爸，妈妈知道会发生什么事，所以她让我来接你。”“对我们来说，这个故事的寓意是，只有当所有相关方的记忆都是可靠的时，常识才能起作用52(Ann她知道鲍勃知道安知道研讨会的事，因为在后一种情况下，她会感到有压力。他可能会安排其他方法，比如让一个学生告诉她，但不说这是鲍勃的信息，而不是告诉她他的谈话，假设一个行人正在过马路，看到一辆汽车向他驶来。在很多城市都有，波士顿，那不勒斯，等等，行人会假装没有注意到汽车，从而防止Kd Kp（C），其中C代表汽车，d是司机，p是行人。如果司机知道行人知道了，他可能会咄咄逼人地开车，试图胁迫行人逃跑或撤退。但如果他不知道行人知道，他会更加谨慎。虽然社会问题是迷人的，并在其他地方解决（Cf。[13])在这篇文章中，我们将集中讨论知识的技术方面人们仍然会问，在不同的交流环境下，可能产生的不同层次的知识是什么？2分布式系统注：以下大多数结果都是与Paul Krasucki联合的，除非另有说明，完整的证明可在[14]中找到我们假设有nite个进程，1;：; n，它们通过异步消息或广播相互计算和通信。我们的网络假设是全连接的（每个进程到其他进程都有一个通道）。异步通信由两个阶段组成：发送和接收。所有发送的消息最终都被传递（并且它们按照发送的顺序被传递），但是延迟（传输时间）可以任意长。广播是完全可靠的同步通信，其中所有涉及的进程同时接收其中一个进程发送的消息现在我们正式指定我们的模型类。设N= f1;：; n g是所有处理器的集合。每个处理器i都有许多可能的初始状态4 如果网络没有完全连接，那么由于缺乏通信能力，某些级别的知识可能无法实现，例如。如果一个处理器是孤立的（不能与任何人通信），那么其他进程就不能从该进程学习任何东西。有趣的问题出现在有向网络的情况下，其中每个进程都可以与其他进程通信，但某些通信必须是间接的（通过其他进程）。我们不会在这里分析这个案例。5 这两种传播可以看作是两种传播媒介例如邮件系统（异步）和电话线（同步）。由于我们允许同时在两个以上的进程之间进行同步通信，我们的电话系统必须具有“会议呼叫”功能。53nn我我我v. 每个初始状态都是一串0和1（v2 f0; 1g）。i的初始状态集表示为yVi。 全局初始状态的集合是V=Qi= 1Vi。从现在开始我们将使用小写字母来表示所有相关的一个单一的过程。在涉及所有进程的情况下将使用大写字母（例如，vi是 处 理 器 i 的 初 始 状 态 ， 而 V 是 整 个 系 统 的 初 始 配 置 ： V=（v1;：;vn））。事件：Ei表示处理器i可以参与的所有事件的集合（i本地的事件）。有以下类型的事件（或操作）：(i) Li：局部计算步骤。(ii) s（i; j; m）：向处理器j发送消息m，j 2N。(iii) r（j; i; m）：从处理器j接收消息m，j 2N。(iv) bc（i; U; m）：向一组处理器U，i，2UN发送广播m。同一事件是一组进程U接收广播m。Ei= Li[fs（i; j; m）jm2M; j2Ng[fr（j; i; m）jm2M; j2Ng[fbc（i; U; m）jm2M; i;j2U Ng[fbc（i; U; m）jm2M; i2U N g We定义了我们系统中的全局事件集G。GQi=1（Ei[fnu ll g）（carbohydrateprop oduct）s.t. 如果（e1;：;ei;：;en）2G对于某些i，e=bc（j;U;m）则对所有i0 2U，e0 =bc（j;U; m）。 如果对 于 某 个 i ，e=nu ll，这意味着在这一点上，在i处没有局部事件。请注意，null不局 限 于 任 何 进 程 。 我们用 符 号 （ G ） i 表 示 G 的 第 i 个 坐 标 ， so（e1;：;ei;：;en）i=ei.历史：历史（运行）是一个输入值，后面跟着一系列事件。让我们把系统所有可能的历史的集合称为协议P。所以P V; G. 在获取历史的初始片段时，协议总是关闭的：H2P意味着每个H 即H的初始段在P中。我们将要求，对于每个协议中每个历史中的每个接收，只有一个相应的发送，并且它发生在接收之前（这种条件我们将称为时间一致性）。我们认为两个历史H和H0 它们以相同的输入值开始。我们可以定义连接 兼容的历史：如果H=V;G;：;G，且H=V;G0;： ;G0，则H是级联1 1k21l的H 且HiH=V;G;：：;G;G0;： ;G0，1 21k1l局部历史是全局历史在局部历史集合上的投影。处理器的事件“他们忘记了我们假设一个全局事件（时钟的滴答声）发生了，即使在某个特定时刻没有局部事件发生给定i和全局历史H，由i所见的事件组成的局部历史hi是唯一定义的，我们让i成为从H到hi的地图。本地历史是处理器看到的所有内容，因此对应于同一本地历史hi的所有全局历史对处理器来说看起来都是相同的54U00我我我我I.注意，i（H）的长度小于或等于H的长度。事实上，长度（i（H））=长度（H）i在H中的i上没有空事件。对于每个i，我们可以在全局历史集合上定义一个等价关系：HiHii（H）=i（H）将这个关系推广到群U，设HH0存在一个链H=H; H;：：;H=H0 对于所有的i k的组中获得任何新事实的公共知识。引用[1] J. Barwise，《共同知识的三种观点》，载于TARK-2，Ed. M。Vardi，Morgan Kaufmann 1988，pp. 369{380.[2] 钱 迪 ·M 和 米 斯 拉 ·J“How Processes Learn” ， Proceedings of 4th ACMConference on Principles of Distributed Computing（1985），第204页。[3] H. H. Clark和C.R. 马歇尔，夜间参考和相互知识，在话语理解的要素，编辑。Joshi，Webber and Sag，剑桥联合Press，1981.[4] M. Fischer和N. Immerman，\分布式系统知识基础，耶鲁大学技术。YALEU/DCS/TR-450号报告，1985年12月[5] 《知识与信仰》，康奈尔大学出版社。Press，1962.[6] Halpern和Y. 摩西，知识与公共知识a分布式环境，Proc.3rd ACMSymposium on Distributed Computing1984 pp. 50{61.[7] J. Halpern 和 L.Zuck ， A Little Knowledge Goes a Long Way ， Proc. 6thPODC，1987，pp.269{280.n160[8] D.《约定，一个哲学研究》，哈佛大学出版社。Press，1969.[9] R. Marvin，M. Greenberg和D.莫斯勒，“概念视角思维的早期发展”，儿童发展，47（1976）511。[10] Y. 摩 西 和 M. Tuttle ， Programming Simultaneous Actions using CommonKnowledge，Research Report MIT/LCS/TR-369（1987）。[11] R. Parikh，“知识和逻辑全知问题”，ISMIS-87，北荷兰，pp。432{439.[12] R. Parikh，“Finite and In Nite Dialogues”，Proceedings of a Workshop onLogic and Computer Science，ed. Moschovakis，Sprinter 1991，481{98.[13] R. Parikh，\Social Software”，将于2002年9月发表在Synthese[14] R.Parikh 和 P.Krasucki ， “Levelsofknowledgeindistributedcomputing”，Sadhana {Proc.Ind.Acad. Sci. 17（1992）pp. 167{191.[15] R. Parikh 和 R. Ramanujam ， Distributed Computing and the Logic ofKnowledge，Logics of Programs1985，Springer LNCS 193，256{268.[16] R. Schank 和 R.Abelson ， Plans ， Goals ， and Understanding ， ErlbaumHillsdale，NJ（1977）.[17] C. Steinsvold和R. Parikh，“儿童心理学中某些现象的模态分析”，符号逻辑通报，2002年3月，逻辑讨论会'01，第158页。[18] C. Steinsvold，“信任和其他模态现象”，研究报告，纽约市立大学研究生中心，2002年2月[19] H. Wimmer和J. Perner，“关于信念的信念：幼儿对欺骗理解中错误信念的表征和约束功能”，认知，13（1983）103{128。