nach oben

Journal of Logic, Language and Information

Erschienen in:

01.07.2013

On the Origin of Ambiguity in Efficient Communication

verfasst von: Jordi Fortuny, Bernat Corominas-Murtra

Erschienen in: Journal of Logic, Language and Information | Ausgabe 3/2013

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

This article studies the emergence of ambiguity in communication through the concept of logical irreversibility and within the framework of Shannon’s information theory. This leads us to a precise and general expression of the intuition behind Zipf’s vocabulary balance in terms of a symmetry equation between the complexities of the coding and the decoding processes that imposes an unavoidable amount of logical uncertainty in natural communication. Accordingly, the emergence of irreversible computations is required if the complexities of the coding and the decoding processes are balanced in a symmetric scenario, which means that the emergence of ambiguous codes is a necessary condition for natural communication to succeed.

Nächster Artikel The Dynamification of Modal Dependence Logic

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Nur mit Berechtigung zugänglich

It is desirable, but not mandatory. As noted by Thomason in his ‘Introduction’ (Montague 1974, Chapter 1), “[A] by-product of Montague’s work (...) is a theory of how logical consequence can be defined for languages admitting syntactic ambiguity. For those logicians concerned only with artificial languages this generalization will be of little interest, since there is no serious point to constructing an artificial language that is not disambiguated (p. 4, note 5)” if the objective is to characterize logical notions such as consequence. However, this generalization is relevant for the development of ‘Universal Grammar’ in Montague’s sense, i.e., for the development of a general and uniform mathematical theory valid for the syntax and semantics of both artificial and natural languages.

If \(\delta \) is not a function from \(\textit{Q} \times \varSigma \) to \(\textit{Q}\times \varSigma \times \left\{ \textit{L}, \textit{R}, \square \right\} \) but rather a subset of (\(\textit{Q} \times \varSigma \times \textit{Q} \times \varSigma \times \left\{ \textit{L}, \textit{R}, \square \right\} )\), then \(\mathcal TM \) is non-deterministic. This means that non-deterministic \(\mathcal TM \)s differ from deterministic \(\mathcal TM \)s in allowing for the possibility of assigning different outputs to one input. For simplicity we will consider in our argumentation only deterministic \(\mathcal TM \)s. Note that this does not entail any loss of generality, since all non-deterministic \(\mathcal TM \)s can be simulated by a deterministic \(\mathcal TM \), although it seems that the deterministic \(\mathcal TM \) requires exponentially many steps in n to simulate a computation of n steps by a non-deterministic \(\mathcal TM \) (cfr. Lewis and Papadimitriou 1997, pp. 221–227).

The basic idea is that an irreversible computer can always be made reversible by having it save all the information it would otherwise lose on a separate extra tape that is initially blank. As Benett shows, this can be attained “without inordinate increase in machine complexity, number of steps, unwanted output, or temporary storage capacity”. We refer the interested reader to Bennett (1973) for a detailed proof and illustration of this result.

Throughout the paper, \(\log \equiv \log _2\).

In the context of this section, complexity has to be understood in the sense of Kolmogorov complexity. Given an abstract object, such a general complexity measure is the length, in bits, of the minimal program whose execution in a Universal Turing machine generates a complete description of the object. In the case of codes where the presence of a given signal is governed by a probabilistic process, it can be shown that Kolmogorov complexity equals (up to an additive constant factor) the entropy of the code (Cover and Thomas 1991).

Equations of this kind have been obtained in the past through different approaches; cfr. Harremoës and Topsœ (2001) and Ferrer-i-Cancho and Solé (2003).

Notice that, if the Turing machine is deterministic, every input generates one and only one output. The problem may arise during the reversion process, if the computations are logically irreversible.

Ash, R. B. (1990). Information theory. New York: Dover Publications.

Bennett, C. (1973). Logical reversibility of computation. IBM Journal of Research and Development, 17(6), 525–532.CrossRef

Bennett, C. (2008). Notes on Landauer’s principle, reversible computation, and Maxwell’s Demon. Studies In History and Philosophy of Science Part B: Studies in History and Philosophy of Modern Physics, 34(3), 501–510.CrossRef

Bennett, C., & Landauer, R. (1985). The fundamental physical limits of computation. Scientific American, 253(1), 38–46.CrossRef

Chomsky, N. (2008). On phases. In R. Freidin, C. P. Otero, & M. L. Zubizarreta (Eds.), Foundational issues in linguistic theory: Essays in honor of Jean-Roger Vergnaud. Cambridge, MA: The MIT Press.

Corominas-Murtra, B., Fortuny, J., & Solé, R. V. (2011). Emergence of Zipf’s law in the evolution of communication. Physical Review E, 83(3), 036–115.CrossRef

Cover, T. M., & Thomas, J. A. (1991). Elements of information theory. New York: Wiley.CrossRef

Ferrer-i-Cancho, R., & Solé, R. V. (2003). Least effort and the origins of scaling in human language. Proceedings of the National Academy of Science, 100, 788–791.CrossRef

Harremoës, P., & Topsœ, F. (2001). Maximum entropy fundamentals. Entropy, 3, 191–226.CrossRef

Ladyman, J., Presnell, S., Short, A., & Groisman, B. (2007). The connection between logical and thermodynamic irreversibility. Studies In History and Philosophy of Science Part B: Studies In History and Philosophy of Modern Physics, 38(1), 58–79.CrossRef

Landauer, R. (1961). Irreversibility and heat generation in the computing process. IBM Journal of Research and Development, 5(3), 183–191.CrossRef

Lewis, H. R., & Papadimitriou, C. H. (1997). Elements of the theory of computation. Upper Saddle River, NJ: Prentice Hall.

Montague, R. (1974). Formal philosophy: Selected papers of Richard Montague, edited and with an introduction by Richmond Thomason. New Haven: Yale University Press.

Toffoli, T. (1980). Reversible computing. In J. de Bakker & J. van Leeuwen (Eds.), Automata, languages and programming. Berlin: Springer.

Wang, E., & Steels, L. (2008). Self-interested agents can bootstrap symbolic communication if they punish cheaters. In A. D. M. Smith, K. Smith, & R. Ferrer-i-Cancho (Eds.), The evolution of language: Proceedings of the 7th international conference (EVOLANG7). Singapore: World Scientific Publishing.

Wittgenstein, L. (1922/1961). Tractatus logico-philosophicus. London: Routledge.

Zipf, G. (1965). Human behavior and the principle of least effort: An introduction to human ecology. New York: Hafner Publishing.

Titel: On the Origin of Ambiguity in Efficient Communication
verfasst von: Jordi Fortuny
Bernat Corominas-Murtra
Publikationsdatum: 01.07.2013
Verlag: Springer Netherlands
Erschienen in: Journal of Logic, Language and Information / Ausgabe 3/2013
Print ISSN: 0925-8531
Elektronische ISSN: 1572-9583
DOI: https://doi.org/10.1007/s10849-013-9179-3

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 3/2013

Inferential Conditionals and Evidentiality

Linguistic and Visual Cognition: Verifying Proportional and Superlative Most in Bulgarian and Polish

The Dynamification of Modal Dependence Logic

An Analytic Tableaux Model for Deductive Mastermind Empirically Tested with a Massively Used Online Learning System

Premium Partner