Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR08-095 | 13th February 2009 00:00

Universal Semantic Communication II: A Theory of Goal-Oriented Communication Revision of: TR08-095

RSS-Feed




Revision #1
Authors: Brendan Juba, Madhu Sudan
Accepted on: 13th February 2009 00:00
Downloads: 2877
Keywords: 


Abstract:

We continue the investigation of the task of meaningful
communication among intelligent entities (players, agents) without any
prior common knowledge. Our generic thesis is that such communication is
feasible provided the goals of the communicating players are verifiable
and compatible. In a previous work we gave supporting evidence for one
specific goal---where one of the players wished to solve a hard
computational problem and communicated with the other in the hope of
finding a solution.

In this work we initiate a "generic" study of the goals of communication.
We present two definitions: one of a "generic" meta-goal, which captures
the (potentially unrealizable) wishes of communicating agents, and the
other being a "generic" syntactic goal, which captures effects that can be
observed by an agent. We then show, under some technical conditions, that
those meta-goals that have corresponding syntactic versions are also
universally achievable, i.e., achievable when the two communicators do not
(necessarily) share a common language.

We also show how our formalism captures a variety of commonplace examples
of goals of communication, including simple control-oriented goals that
aim to effect a remote physical action by communication, as well as more
subtle intellectual goals where the communicator's intent is mostly to
gain knowledge. Our examples from the latter class include a variety of
settings where meta-goals differ significantly from syntactic goals.


Paper:

TR08-095 | 31st October 2008 00:00

Universal Semantic Communication II: A Theory of Goal-Oriented Communication





TR08-095
Authors: Brendan Juba, Madhu Sudan
Publication: 31st October 2008 20:07
Downloads: 1624
Keywords: 


Abstract:

We continue the investigation of the task of meaningful communication among intelligent entities (players, agents) without any prior common language. Our generic thesis is that such communication is feasible provided the goals of the communicating players are verifiable and compatible. In a previous work we gave supporting evidence for this thesis where the goal for one of the players was computational (he wished to solve a hard computational problem).

In this work we broaden this study to "generic" goals for communication, and initiate a formal study of the features of such goals. We assert, almost tautologically, that generic goals capture every possible goal of communication. In particular, we give a formal distinction between two types of goals: intellectual and control-oriented. We give an explicit condition on the goal that makes communication essential to its satisfaction. We show that goals are universally achievable if and only if they have a "verifiable" related goal. Control-oriented goals tend to be verifiable immediately. We show how a rich variety of intellectual goals also have verifiable related goals.



ISSN 1433-8092 | Imprint