Archive for the ‘Computation’ Category

A Rosetta Stone

December 6, 2017

Abstract of Physics, Topology, Logic and Computation: A Rosetta Stone by John Baez and Michael Stay:

In physics, Feynman diagrams are used to reason about quantum processes. In the 1980s, it became clear that underlying these diagrams is a powerful analogy between quantum physics and topology: namely, a linear operator behaves very much like a “cobordism”. Similar diagrams can be used to reason about logic, where they represent proofs, and computation, where they represent programs. With the rise of interest in quantum cryptography and quantum computation, it became clear that there is extensive network of analogies between physics, topology, logic and computation. In this expository paper, we make some of these analogies precise using the concept of “closed symmetric monoidal category”. We assume no prior knowledge of category theory, proof theory or computer science.

  • Physics
  • Logic
  • Topology
  • Computation

Perhaps Category Theory is a “Fifth Essence”?

Further Reading:

http://math.ucr.edu/home/baez/rosetta/rose3.pdf

https://arxiv.org/abs/0903.0340

[*9.168, *10.50]

<>

Advertisements

Speak, Listen, Write, and Read

December 3, 2017

Here’s another simple fourfold and maybe sixfold.

Speaking, Listening, Writing, and Reading are commonly presented together in elementary education as interrelated language skills. One is speaking for a listener and one is writing for a reader. One is listening to a speaker and one is reading a writer.

In the computer age another pair needs to be mentioned, that of programming for computers and the execution or running of that code by the computer. In a way, this new pair doesn’t fit, since one is writing code for computers, not people. And the execution of the program is not performed by a person, but by a computer.

(That’s not entirely true. Programs are also written for other human programmers in mind so that they can debug or maintain or modify the code if the original programmer isn’t available. Structured programming is one method to simplify the logical organization of the program so that others can comprehend it more readily. Object oriented programming is another method to allow multiple programmers to work independently without conflict.)

  • Speak – Listen
  • Write – Read
  • Program – Execute

But perhaps there is a different way to understand these duals. A speaker understands that a listener is following their speech by their response. A writer understands that a reader is comprehending their writing by their response. A programmer understands that a computer is ‘understanding’ the code by its response or output when the program is run.

Also, one can consider speech and writing to be encodings of thoughts into physical representations, and listening and reading to be decoding of the representations back into thoughts. Running or executing a program is not really decoding, or is it? But it is something like processing the speech or writing, like a computer is processing the program.

One might say that listening and reading are like processing the speech and text as programs on the computer of our brains. They are normally thought to be processed as data, as in Natural Language Processing, but it is an interesting twist if one considers them as programs. (Actually, I just recalled that the 1992 science-fiction novel “Snow Crash” by Neal Stephenson used this notion.)

To program effectively the programmer must execute their code in their mind, at least piecemeal and partially, just as a speaker or a writer must listen as they speak and read over what they have written. They can’t understand the full effect of the program’s execution, especially once the program becomes larger than a few statements, just as the full effect of speech or writing that is being processed by another person cannot be completely understood.

Not considered are computers themselves writing programs for other computers to “read” or execute. As the science of artificial intelligence becomes mature, computers writing and reading among themselves may become a common thing. Wasn’t there a news article about that recently? They pulled the plug on that pretty fast.

As digital assistants become more ubiquitous, they are fully participating in our language games of speaking, listening, writing, and reading. Will these so-called virtual assistants program for us next, as in Automatic Programming? That day may already be here.

Further Reading:

https://www.englishclub.com/learn-english/language-skills.htm

https://en.wikipedia.org/wiki/Natural_language_processing

https://www.theatlantic.com/technology/archive/2017/06/artificial-intelligence-develops-its-own-non-human-language/530436/

https://en.wikipedia.org/wiki/Automatic_programming

N. Katherine Hayles / My Mother was a Computer: digital subjects and literary texts

Neal Stephenson / Snow Crash

https://en.wikipedia.org/wiki/Virtual_assistant_(artificial_intelligence)

Images:

https://www.google.com/search?q=speak+listen+write+read&tbm=isch&tbo=u&source=univ&sa=X&ved=0ahUKEwi14LrrsarXAhUG6CYKHaugBH4QsAQIVQ

[*9.50, *10.36, *10.46]

<>

The Duality of Time and Information, V3

October 1, 2017

 

The states of a computing system bear information and change time, while its events bear time and change information.

from The Duality of Time and Information by Vaughn Pratt

The most promising transformational logic seems to us to be Girard’s linear logic.

— from Rational Mechanics and Natural Mathematics by Vaughn Pratt

 

Here we have three duals:

  • Information – Time
  • States – Events
  • Bear – Change

Further Reading:

Vaughan Pratt / The Duality of Time and Information http://boole.stanford.edu/pub/dti.pdf

Vaughan Pratt / Time and Information in Sequential and Concurrent Computation http://boole.stanford.edu/pub/tppp.pdf

Vaughan Pratt / Rational Mechanics and Natural Mathematics http://chu.stanford.edu/guide.html#ratmech

[*5.170]

<>

A Digital Universe, V2

August 9, 2017

A digital universe – whether 5 kilobytes or the entire Internet – consists of two species of bits: differences in space, and differences in time. Digital computers translate between these two forms of information – structure and sequence – according to definite rules. Bits that are embodied as structure (varying in space, invariant across time) we perceive as memory, and bits that are embodied as sequence (varying in time, invariant across space) we perceive as code. Gates are the intersections where bits span both worlds at the moments of transition from one instant to the next.

— George Dyson, from Turing’s Cathedral

Further Reading:

George Dyson / Turing’s Cathedral: the origins of the digital universe

Notes:

Embodied as Structure, Perceived as Memory

Invariant across Time: ¬ΔT
Varying in Space: ΔS

Embodied as Sequence, Perceived as Code

Varying in Time: ΔT
Invariant across Space: ¬ΔS

https://equivalentexchange.wordpress.com/2012/04/12/a-digital-universe/

[*7.82, *7.83, *7.153, *10.14]

<>

Propositions as Types

February 14, 2016

sq_propositions_as_types3For almost 100 years, there have been linkages forged between certain notions of logic and of computation. As more associations have been discovered, the bonds between the two have grown stronger and richer.

  • Propositions in logic can be considered equivalent to types in programming languages.
  • Proofs of propositions in logic can be considered equivalent to programs of given type in computation.
  • The simplification of proofs of propositions in logic can be considered equivalent to the evaluation of programs of types in computation.

The separate work of various logicians and computer scientists (and their precursors) can be paired:

  • Gerhard Gertzen’s work on proofs in intuitionistic natural deduction and Alonzo Church’s work on the simply typed lambda calculus.
  • J. Roger Hindley and Robin Milner’s work on type systems for combinatory logic and programming languages, respectively.
  • J. Y. Girard and John Reynold’s work on the second order lambda calculus and parametric polymorphic programs, respectively.
  • Haskell Curry’s and W. A. Howard’s work on the overall correspondence between these notions of proofs as programs or positions as types.

Logic and computation are the sequential chains of efficient causation and actions. Propositions and types are the abstract grids of formal causation and structures. Proofs and programs are the normative cycles of final causation and functions. Simplification and evaluation are the reductive solids of material causation and parts.

References:

Philip Wadler / Propositions as Types, in Communications of the ACM, Vol. 58 No. 12 (Dec 2015) Pages 75-85.

http://cacm.acm.org/magazines/2015/12/194626-propositions-as-types/fulltext

Preprint at

http://homepages.inf.ed.ac.uk/wadler/papers/propositions-as-types/propositions-as-types.pdf

Also see:

http://www.drdobbs.com/old-ideas-form-the-basis-of-advancements/184404384

https://en.wikipedia.org/wiki/Hindley%E2%80%93Milner_type_system

https://en.wikipedia.org/wiki/System_F

https://en.wikipedia.org/wiki/Curry%E2%80%93Howard_correspondence

[*9.92-9.94]

<>

 

The Duality of Time and Information, V2

May 2, 2013

The states of a computing system bear information and change time, while its events bear time and change information.

from The Duality of Time and Information by Vaughn Pratt

The most promising transformational logic seems to us to be Girard’s linear logic.

— from Rational Mechanics and Natural Mathematics by Vaughn Pratt

Here we have three duals: information – time, state – event, and bear – change.

References:

Vaughan Pratt / The Duality of Time and Information http://boole.stanford.edu/pub/dti.pdf

Vaughan Pratt / Time and Information in Sequential and Concurrent Computation http://boole.stanford.edu/pub/tppp.pdf

Vaughan Pratt / Rational Mechanics and Natural Mathematics http://chu.stanford.edu/guide.html#ratmech

[*5.170]

<>

The Curry-Howard Correspondence

August 21, 2012

The Curry-Howard Correspondence reveals a close correspondence between the constituents of Logic and of Programming. Also known as the Formulas as Types and the Proofs as Programs interpretations.

Existential Quantification (∃) of Logic corresponds to the Generalized Cartesian Product type (∑) of Programming. Universal Quantification (∀) of Logic corresponds to the Generalized Function Space type (∏) of Programming. Conjunction (⋀) of Logic corresponds to the Product type (×) of Programming. Disjunction (⋁) of Logic corresponds to the Sum type (+) of Programming.

There are associations between the Curry-Howard Correspondence and the fourfolds of the Square of Opposition, Attraction and Repulsion, and of course Linear Logic.

http://en.wikipedia.org/wiki/Curry-Howard_correspondence

<>

A Digital Universe

April 12, 2012

A digital universe – whether 5 kilobytes or the entire Internet – consists of two species of bits: differences in space, and differences in time. Digital computers translate between these two forms of information – structure and sequence – according to definite rules. Bits that are embodied as structure (varying in space, invariant across time) we perceive as memory, and bits that are embodied as sequence (varying in time, invariant across space) we perceive as code. Gates are the intersections where bits span both worlds at the moments of transition from one instant to the next.

— George Dyson, from Turing’s Cathedral

George Dyson / Turing’s Cathedral: the origins of the digital universe

[*7.82, *7.83, *7.153]

<>

The Four Basic Electronic Components

June 10, 2011

A fourfold has recently been in the news. The physical realization of the memristor completes the four basic electronic components, along with the resistor, capacitor, and inductor. Theorized to exist since 1971, the memristor may revolutionize computational devices.

References:

http://en.wikipedia.org/wiki/Memristor

[*6.126-*6.128]

<>

The Duality of Time and Information

August 26, 2010

The states of a computing system bear information and change time, while its events bear time and change information.

from The Duality of Time and Information by Vaughn Pratt

The most promising transformational logic seems to us to be Girard’s linear logic.

— from Rational Mechanics and Natural Mathematics by Vaughn Pratt

References:

Vaughan Pratt / The Duality of Time and Information http://boole.stanford.edu/pub/dti.pdf

Vaughan Pratt / Time and Information in Sequential and Concurrent Computation http://boole.stanford.edu/pub/tppp.pdf

Vaughan Pratt / Rational Mechanics and Natural Mathematics http://chu.stanford.edu/guide.html#ratmech

 [*5.170]

<>