Universal semantic communication

Medientyp: E-Book

Titel: Universal semantic communication

Beteiligte: Juba, Brendan [VerfasserIn]

Erschienen: Berlin; Heidelberg [u.a.]: Springer, 2011

Ausgabe: Online-Ausg.

Umfang: Online-Ressource (1 online resource (404 p.))

Sprache: Englisch

ISBN: 9783642232978

RVK-Notation: ST 306 : Natürliche Sprachverarbeitung

Schlagwörter: Mensch-Maschine-Kommunikation > Kommunikationsprotokoll > Semantik > Universalsprache > Berechnungstheorie > Algorithmische Lerntheorie > Komplexitätstheorie > Formale Methode

Entstehung:

Anmerkungen: Description based upon print version of record

Beschreibung: Universal Semantic Communication; Foreword by Oded Goldreich; Preface; Contents; 1 Introduction; 1.1 Technical motivation; 1.2 Limits of our scope, or: what this book is not about; 1.3 History and prior work; 1.3.1 Prior work on CETI; 1.3.2 Formal theories of communication problems; 1.3.3 Similar work in other areas; 1.4 Overview of our contributions; 1.4.1 Philosophical context; 1.4.2 An example: computational goals; 1.4.3 Overview; 1.4.4 Contributions of this book in the context of its relationship to other work; 2 Theory of finite goal-oriented communication

2.1 An informal overview of the theory2.1.1 Goals: a formal explication of meaning; 2.1.2 Sensing functions; 2.1.3 Capabilities and limits of universal users; 2.2 Model of communication and goals; 2.2.1 Agents: users, servers, and their environment; 2.2.2 Goals of communication; 2.2.3 Universal users; 2.2.4 Helpful servers; 2.3 Sensing and universality; 2.3.1 Sensing: safety and viability; 2.3.2 Sensing is necessary and sufficient for finite goals; 2.3.3 Extensions and variants of sensing: alternative constructions; 2.3.4 Safety requirements in the basic universal setting

3 Verifiable goals for communication3.1 Notation and definitions; 3.2 Control-oriented goals; 3.2.1 Transparent goals; 3.2.2 Searching; 3.3 Computational goals; 3.3.1 Main definitions in this setting; 3.3.2 Characterization of functions with polynomial time universal protocols; 3.3.3 Main consequences of the characterization; 3.3.4 Beyond PSPACE-completeness: more examples of universal protocols for computational problems; 3.3.5 Communication in spite of indeterminacy; 3.4 Intellectual curiosity; 3.4.1 A primer on computational depth; 3.4.2 Formalizing a goal of intellectual curiosity

3.4.3 Constructing universal reviewers: sensing functions for goals of intellectual curiosity3.5 Tests; 3.5.1 A test of computational ability; 3.5.2 Examiner strategy for a test of computational ability; 3.5.3 Promises and verifiability; 4 Conditions for efficiency in finite executions; 4.1 Running time lower bounds via passwords; 4.1.1 Lower bound for nontrivial goals; 4.1.2 Extension to parameterized nontriviality; 4.2 A Bayesian refinement of helpfulness; 4.2.1 Basic notions: priors and benchmarks; 4.2.2 Uniform viability; 4.2.3 An efficient universal protocol for close priors

4.3 Effective conditions for efficient users4.3.1 Servers with a designated class of properly functioning states; 4.3.2 Effective refinements of sensing; 4.3.3 A universal user for servers that are easy to use and hard to break; 4.4 Lower bounds in the absence of a common prior; 4.4.1 A generic lower bound when no common prior exists; 5 Computational complexity of goals; 5.1 Generic complexity classes for interactive computation; 5.1.1 Model of interactive computation; 5.1.2 Bounded resources and simulation; 5.1.3 Composition; 5.1.4 Basic agents: the toolkit

5.2 On the computational complexity of goal-oriented communication

Is meaningful communication possible between two intelligent parties who share no common language or background? In this work, a theoretical framework is proposed in which it is possible to address when and to what extent such semantic communication is possible: such problems can be rigorously addressed by explicitly focusing on the goals of the communication. Under this framework, it is possible to show that for many goals, communication without any common language or background is possible using universal protocols. This work should be accessible to anyone with an undergraduate-level knowled

Universal semantic communication - [Online-Ausg.]

Merkliste

Nur in Feld suchen:

Zuletzt gesuchte Begriffe: