Universal semantic communication I

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Universal semantic communication I

Full text

Pdf (248 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the 40th annual ACM symposium on Theory of computing table of contents

Victoria, British Columbia, Canada

SESSION: 4A table of contents

Pages 123-132

Year of Publication: 2008

ISBN:978-1-60558-047-0

Authors

Brendan Juba	MIT CSAIL, Cambridge, MA, USA
Madhu Sudan	MIT CSAIL, Cambridge, MA, USA

Sponsors

ACM: Association for Computing Machinery
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 12, Downloads (12 Months): 92, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1374376.1374397 What is a DOI?

ABSTRACT

Is it possible for two intelligent beings to communicate meaningfully, without any common language or background? This question has interest on its own, but is especially relevant in the context of modern computational infrastructures where an increase in the diversity of computers is making the task of inter-computer interaction increasingly burdensome. Computers spend a substantial amount of time updating their software to increase their knowledge of other computing devices. In turn, for any pair of communicating devices, one has to design software that enables the two to talk to each other. Is it possible instead to let the two computing entities use their intelligence (universality as computers) to learn each others' behavior and attain a common understanding? What is 'common understanding?' We explore this question in this paper.

To formalize this problem, we suggest that one should study the 'goal of communication:' why are the two entities interacting with each other, and what do they hope to gain by it? We propose that by considering this question explicitly, one can make progress on the question of universal communication.

We start by considering a computational setting for the problem where the goal of one of the interacting players is to gain some computational wisdom from the other player. We show that if the second player is "sufficiently" helpful and powerful, then the first player can gain significant computational power (deciding PSPACE complete languages).

Our work highlights some of the definitional issues underlying the task of formalizing universal communication, but also suggests some interesting phenomena and highlights potential tools that may be used for such communication.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	L. Babai, L. Fortnow, and C. Lund. Non-deterministic exponential time has two-prover interactive protocols. Computational Complexity, 1(1):3--40, 1991.
	2	M. Blum , S. Kanna, Designing programs that check their work, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.86-97, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73015]
	3	H. Freudenthal. LINCOS: Design of a Language for Cosmic Intercourse. North Holland Publishing Company, Amsterdam, 1960.
	4	O. Goldreich. Personal communication, February 2007.
	5	Oded Goldreich , Dana Ron, On universal learning algorithms, Information Processing Letters, v.63 n.3, p.131-136, Aug. 14, 1997 [doi>10.1016/S0020-0190(97)00117-8]
	6	S. Goldwasser , S. Micali , C. Rackoff, The knowledge complexity of interactive proof systems, SIAM Journal on Computing, v.18 n.1, p.186-208, Feb. 1989 [doi>10.1137/0218012]
	7	M. Kharitonov , A. V. Goldberg , M. Yung, Lower bounds for pseudorandom number generators, Proceedings of the 30th Annual Symposium on Foundations of Computer Science, p.242-247, October 30-November 01, 1989 [doi>10.1109/SFCS.1989.63485]
	8	L. A. Levin. Universal search problems. Probl. Inform. Transm., 9:265--266, 1973.
	9	Carsten Lund , Lance Fortnow , Howard Karloff, Algebraic methods for interactive proof systems, Journal of the ACM (JACM), v.39 n.4, p.859-868, Oct. 1992 [doi>10.1145/146585.146605]
	10	M. Minsky. Communication with alien intelligence. In E. Regis, editor, Extraterrestrials: Science and Alien Intelligence, pages 117--128. Cambridge University Press, New York, USA, 1985.
	11	W. V. O. Quine. Word and Object. MIT Press, Cambridge, 1960.
	12	Adi Shamir, IP = PSPACE, Journal of the ACM (JACM), v.39 n.4, p.869-877, Oct. 1992 [doi>10.1145/146585.146609]
	13	C. E. Shannon. A mathematical theory of communication. Bell System Technical Journal, 27:379--423, 623--656, 1948.
	14	Andrew Chi-Chih Yao, Some complexity questions related to distributive computing(Preliminary Report), Proceedings of the eleventh annual ACM symposium on Theory of computing, p.209-213, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804414]