Developers Club geek daily blog

1 year, 9 months ago
камень-ножницы-бумага (на ауребеш) At the end of last year the Google Translate Aurebesh added support of "Galactic language" to an output of a new episode of "Star wars". The truth it turned out that at the choice of this language just there is transfer into English. If to use Chrome or Firefox, then there is a font in which instead of Latin characters aurebesh are substituted, and in IE without special cunnings the English text is output.

Began to remember other examples of creation of "languages of strangers". For example, language Klingonov from "Star Trek" is based on Latin too, but at the same time is worked rather out, has the syntax and the dictionary. Languages of the people of Sredizemya from "Lord of the Rings" – in general separate history.

And still there are such languages as the Linkos which is specially developed by Hans Freudental for interplanetary communication and based on the assumption that the mathematics is a universal language of communication for any reasonable beings.

In "The flat world" of Terry Pratchett there are enough languages too, but it seems it is just renamed terrestrial languages. And concerning mathematics as universal language, more pertinently to mention the English biologist Jack Cohen, his coauthor according to the book "Science of the Flat World" who at one conference touched upon rather unexpected subject: "Why you think that newcomers will understand your mathematics? And suddenly they have absolutely other method of thinking?"

I read this quote at James Neyshin, other conferee, professor of university in Hawaii where it also passed. On its website it is possible to find texts of two performances to some extent provoked by the matter: "As newcomers do mathematics" and "Logic of other planets". Can do it and looks not really seriously, especially when different types of logic are attributed by inhabitants of different planets of our solar system. However, here looked for possible references to one function used for creation of reversible valves and with surprise found it in it in the section devoted to logic of inhabitants of Jupiter.

Stone, scissors, paper


What special is in "yupiteriansky logic" and as it is connected with reversible calculations? Neyshin for its description uses a set of three elements designated by characters of R,P,S which correspond to the first letters of the English words for a stone, scissors and paper. The game "stone, scissors, paper" (here too wrote about it and more than once) is known also in Hawaii as "dzyan-ken". By rules of the game one of three objects wins against another proceeding from a cyclic set of preferences. It is usually represented on the pie chart, but it is possible to write also in a line:

S <— R <— P <— S


ножницы-камень-бумага-ножницы

The mathematical character of the relation "precedes" (Unicode 227A) used on the picture is absent in many fonts therefore in the text it is replaced on < —

How it is connected with logic? It is known that if to equate LOZH=0, ISTINA =1, then there corresponds to function "minimum", and "OR" – "maximum". The same acceptance is applied in multiple-valued and fuzzy logic as at such determination many properties of normal logic are automatically executed. So, the task of the relations between elements defines analogs of logic operations. However, at a cyclic set of preferences between tryomya elements some properties should be offered. What to do, other logic.

The table for analog "OR" at such approach looks as
Other ILI R P S
R R P R
P P P S
S R S S

The table for operation "I" is stood similarly
Other And R P S
R R R S
P R P P
S S P S

Reversible calculations


And what with reversible calculations? Already here too wrote about them as, however, and about ternary logic (here, on geektimes, still here) and even together tried to reduce them.

Reversible valves can be useful to a solution of the problem of heat release in processors of the next generations, they are closely connected with the theory of quantum computings. And subject rather interesting in itself. About it much where to esteem, including the references given above so I will try to extend to a subject of already rather known things not especially is possible.

If it is absolutely short, then the valve is reversible when values on inputs can always be recovered on values on outputs. For work with binary data usually use Toffoli or Fredkin's universal valves. Both valves have three inputs and three outputs as, unlike an irreversible case, from reversible binary valves with two inputs it is impossible to create a set for execution of any operation over data.

Let's try to provide reversible analog of a normal valve "OR". Let's assume that it has two inputs (and two outputs, if it has to be reversible), on inputs binary values move, and one of outputs has to issue result of the operation "OR". It turns out that the same value 1 (ISTINA) on this output can turn out at three different combinations on an input: 11, 01, 10. If the second output could have three different values, it could be used for the address of such valve.

So, already rather simple estimates lead to idea to use ternary system at least on one output. And what if to try to work from three values at all inputs and outputs – whether it is possible to receive a reversible valve if to use ternary logic?

The ternary logic of Lukasiewicz is rather widespread. It can be constructed also by the trick which is already mentioned above about a maximum and a minimum if to assume that to the third value there corresponds some number x, 0 < x < 1, например x = 1/2. Получаются хорошо известные троичные таблицы, для «ИЛИ»:
"Ternary ILI" 0 x 1
0 0 x 1
x x x 1
1 1 1 1

For "And":
"Ternary And" 0 x 1
0 0 0 0
x 0 x x
1 0 x 1

Let's assume again that we have a ternary valve with two inputs and two outputs. On the first output one of the functions given above moves. Whether it is possible to pick up function for the second output that the valve was reversible. It appears, it is impossible. The matter is that for any reversible function in 3х3 table describing any input, all values have to meet on three times.

Really, on an input it is possible to give nine possible couples of values
00 01 0x 10 11 1x x0 x1 xx
and as the valve is reversible, and on an output each of these nine couples has to appear at one of combinations on an input. It is visible that in these couples any value of the first (and the second) an element will meet on three times.

That is, three zero, three units, three X. And instead in the table for ternary "OR" it is worth one zero and five units. In the second table for "And" on the contrary, five zero and one unit that too does not approach.

Therefore though reversible ternary valves separately and ternary logic separately are rather widely used, together it is difficult to reduce them. Here also the "alien" logic comes to the rescue. For descriptive reasons we will replace R,P,S on 0,1, $.

0 1 в обозначениях камень-ножницы-бумага

Here the table for "OR"
"Other OR" 0 1 $
0 0 1 0
1 1 1 $
$ 0 $ $

For values 0, 1 it matches with normal "OR", but at the same time possesses already mentioned property necessary for creation of a reversible ternary valve (each value meets on three times). The situation with the table for operation "I" is similar
"Other And" 0 1 $
0 0 0 $
1 0 1 1
$ $ 1 $

Now, to construct complete option of reversible ternary valves it is necessary to pick up still the table for the second, auxiliary output. In normal arithmetics for the address of the max function (a, b) on the second output it would be possible to use b–a. Something similar can be used also in our example
"Other difference" 0 1 $
0 0 $ 1
1 1 0 $
$ $ 1 0

Approached – so the complete ternary reversible valve here will look "OR"
Login 00 01 $0 10 11 $1 $0 $1 $$
Output 00 11 $0 $1 10 $1 01 $$ $0

It is visible that each of nine possible combinations meets on an output one time so operation is reversible. Action of this valve can be described still as follows: it does not change couple 00, $0, rearranging on a cycle seven couples (01, 11, 10, $1, $1, $ $, $0)

So, sevenfold application of a valve will leave any couple of values without changes, and the return operation corresponds to application of six valves in a row. With Toffoli and Fredkin's valves it is simpler, each of them matches the return.

If to give on an input only values zero and unit, then this ternary valve implements normal logic operation "OR". Having set unit on the second input it is possible to use the second output as the operation "NOT" from the first input. In addition, the valve implements the operation "branchings" of the binary value given on the second input if on the first to give zero. So this reversible ternary valve is universal for work with binary data.

The example of a reversible ternary valve is "Also" similar
Login 00 01 $0 10 11 $1 $0 $1 $$
Output 00 01 $$ $0 10 11 $1 $1 $0

This valve does not change couple 00 and 01, rearranging couples on a cycle
($0, $ $, $0, $1, $1, 11, 10, $0)

It is universal for binary operations too, but unlike "OR", it is not enough one such valve for "branching". However, the choice of operation on the second output was rather any. Operation on the first input unambiguously are defined by the choice of three conditions: (1) to execute the necessary logic operation for binary data, (2) to correspond to one of values on an input, (3) not to depend on their shift.

The choice of the second operation is rather natural too and can be used for other models. Let's assume, it is necessary to construct a reversible valve for Lukasiewicz's logic. The problem with it was already described, some values appear in table 3x3 five times, and them has to be equally to make a reversible valve.

Still lizard and Spock


Here it is possible to apply the same idea, as at expansion of binary logic to system from three elements and proceeding from the available problem with five repetitions in the table to ternary logic of Lukasiewicz (0, 1, x), it is necessary to add two more elements ($ and @). Other argument for benefit of five values is connected with use of analog of a difference of b-a for the address of a maximum and a minimum: the difference between three whole values from 0 to 2 can accept five different values from-2 to 2.

Ratios between elements can be represented on the pie chart again or to write in a line
0 <- 1 <- $ <- x <- @ <- 0 <- x <- 1 <- @ <- $ <- 0
The corresponding game is known too. For example, its version was shown in series "Theory of the Big Bang" (the picture with an explanation). Compliances it is possible to select such: 0 - 1 – paper, $ — scissors, @ — a lizard, x — Spock (the native of the planet Vulcan in series "Zvyozdy Way").

камень-ножницы-бумага-ящерица-Спок

It is possible to continue further; for creation of similar pie charts, sets in which quantity of elements to equally prime number especially well approach.

Collective logic and "impossible shooters"


It is necessary to tell that cyclic logic not such "alien". One of the most characteristic examples is connected with Condorcet and Errou's paradoxes relating to a choice problem. The typical description of "paradox of vote" can be found in the book of the Nobel Prize laureate on economy Kenneth Errou "Collective choice and individual values".

Let's consider the choice from three alternatives (for example, elections with three candidates) A, B, C. At the same time, each voting has the certain arranged system of preferences. That is, if the first alternative is more preferable than the second, and the second preferable the third, then the first is more preferable than the third too. The example of problems with the choice arising at violation of this criterion is described further too.

Such arranged preferences are an example of the transitive relations, and operations with similar property are associative, that is, do not depend on arrangement of brackets. The determination of the operation "OR" discussed earlier through a task of the relations of elements well will be approved with idea of the choice: the operation "And OR In" – just the choice between A and B, proceeding from nobody a set of preferences (including a case "And ILI A" which, though it is difficult to call "choice", has quite certain result, A). too

Let someone believe that B is better than A, C better In (and by the criterion given earlier, A is better than C). Let's write this choice as
(1)< B < C
We Will assume A that there are two other ordered sets of preferences
(2)< C < A
B (3) C< A < B
we Will designate shares of voters with the corresponding set of preferences as P1, P2, P3. Then a share, considering that B will be better than A of P1+P3 and believing that B will be better for C than P1+P2, but at this P2+P3 think that A is better than C.

If all P1+P2, P2+P3, P1+P3 values it is more than a half (or that the same, any share of P1, P2, P3 is less than a half), then during the vote of B wins against A, C wins against B, but A wins against C. The cyclic system of collective preferences which in order to avoid misunderstanding we will designate already used icon for the relation without property of transitivity is formed
A < — B < — C < — A.

Even in the presence at each individual of ordered set of preferences, without transitivity the collective choice is not unambiguous any more. The result of elections can depend on an order of carrying out and in general be any. Further the examples of three schemes of elections with a different order of votes leading to a victory of any of three candidates are shown.

Scheme 1
First round: the choice between A and B, wins against B
Second round: the choice between B (won the first stage) and C,
wins against C (the second round and elections)

Scheme 2
First round: the choice between B and C, wins against C
Second round: the choice between C and A, wins against A elections

Scheme 3
First round: the choice between A and C, wins against A
Second round: the choice between B and A, wins against B elections

The same problem can be illustrated as lack of associativity in cyclic system of preferences. Let's designate choice operation as ||

Then the first two schemes correspond to arrangement of brackets

((A || B) || C) = B || C = C, (A || (B || C)) = A || C = A

This article is a translation of the original post at habrahabr.ru/post/274645/
If you have any questions regarding the material covered in the article above, please, contact the original author of the post.
If you have any complaints about this article or you want this article to be deleted, please, drop an email here: sysmagazine.com@gmail.com.

We believe that the knowledge, which is available at the most popular Russian IT blog habrahabr.ru, should be accessed by everyone, even though it is poorly translated.
Shared knowledge makes the world better.
Best wishes.

comments powered by Disqus