Mental Models May Fail When Faced With Self-Referential Descriptors; J.A.I.S.T Vol.66, Issue 10

As promised back in July, Alexandre De Castro’s exploration of involutionary logic negation as applied to Russell’s paradox, has been published as a letter-to-editor in the Journal of the Association for Information Science and Technology; Vol 66, Issue 10.
http://onlinelibrary.wiley.com/mentalmodelsmayfail

NSA; Prepare for the coming Crypto Apocolypse…

D-Wave Systems chip with purported quantum properties.

From arstechnica;
“The National Security Agency is advising US agencies and businesses to prepare for a time in the not-too-distant future when the cryptography protecting virtually all e-mail, medical and financial records, and online transactions is rendered obsolete by quantum computing.

Quantum computers have capabilities that can lay to ruin all of the public-key cryptographic systems currently in use. These capabilities, which aren’t known to be present in the classical computers of today, include the ability to almost instantly find the prime factors of extremely large numbers, using a method called Shor’s algorithm. Quantum computing is also believed to be capable of tackling other mathematical problems classical computers can’t solve quickly, including computing discrete logarithm mod primes and discrete logs over elliptic curves.

The difficulty of factoring and computing discrete log primes and elliptic curve discrete logs play an essential role in cryptographers’ confidence in RSA, elliptic curve cryptography, and other public-key crypto systems. When implemented correctly, most scientists and cryptographers believe that the crypto can’t be defeated with today’s computers before the end of the universe.”

http://arstechnica.com/security/2015/08/nsa-preps-quantum-resistant-algorithms-to-head-off-crypto-apocolypse/

How the NSA backdoored Dual EC PRNG

from projectbullrun.org;

“Abstract. Dual EC is an algorithm to compute pseudorandom numbers starting from some random input. Dual EC was standardized by NIST, ANSI, and ISO among other algorithms to generate pseudorandom numbers. For a long time this algorithm was considered suspicious – the entity designing the algorithm could have easily chosen the parameters in such a way that it can predict all outputs – and on top of that it is much slower than the alternatives and the numbers it provides are more biased, i.e., not random.

The Snowden revelations, and in particular reports on Project Bullrun and the SIGINT Enabling Project, have indicated that Dual EC was part of a systematic effort by NSA to subvert standards.

This paper traces the history of Dual EC including some suspicious changes to the standard, explains how the back door works in real-life applications, and explores the standardization and patent ecosystem in which the standardized back door stayed under the radar.” 

https://projectbullrun.org/dual-ec/documents/dual-ec-20150731.pdf

image; © Rachael Parsons. The BackDoor Gallery @ Room 60 QLD

A Transfinite Shave

A version of this post has been accepted into the Journal of the Association for Information Science and Technology as a letter-to-editor. Congratulations Alex DeCastro!

Tambo University

Russell’s Barber: paradox or (else) pseudoparadox?

Some axioms can be “unprovable truths” of Godel’s incompleteness theorem. Today, we show that Godel’s theorem can be easy to understand in general terms, but hard to understand beyond a typical contradiction, as per Russell’s barber (pseudo) paradox.

Consider the classical Russell’s gedankenexperiment wherein, all the men that live in a village are cleanly shaven. They either shave themselves or they do not. If they do not shave themselves, the village’s only barber must shave them.

Hence there exist two sets: the set of all men who shave themselves and the set of all men who have the barber do it for them.

But, who shaves the barber?

Let us analyze this problem based on Zermelo-Fraenkel’s set theory and Cantor’s set theory.

Zermelo-Fraenkel’s set theory

Take a male barber that lives in the village. He is clean-shaven. Then, either he shaves himself or else he…

View original post 499 more words

EPR-Redux; (We’re so sorry, Uncle Albert!)

2015 marks the 80th. anniversary of the EPR paradox.

“One can give good reasons why reality cannot at all be represented by a continuous field. From the quantum phenomena it appears to follow with certainty that a finite system of finite energy can be completely described by a finite set of numbers (quantum numbers). This does not seem to be in accordance with a continuum theory and must lead to an attempt to find a purely algebraic theory for the representation of reality. But nobody knows how to find the basis for such a theory.” A. Einstein; Appendix 2: The Meaning of Relativity, 1935

In 1935 Albert Einstein, along with two colleagues, Boris Podolsky and Nathan Rosen, published a work known as the EPR paper, challenging the foundations of quantum mechanics. The three scientists argued that extra pieces of information – hidden variables – were necessary to perform the unitary evolution of the wave function and make quantum mechanics a complete theory. In the following, we show that the idea of hidden variables can be understood from the measurement-based implementation of a controlled-NOT (CNOT) quantum gate.

In quantum mechanics, the EPR paradox is a thought experiment which challenges long-held ideas about the completeness of quantum theory. The core of the EPR paradox is that quantum mechanics cannot be both consistent and complete unless hidden variables exist.

The EPR paradox has been strongly debated over for eighty years and almost all of the arguments, including the work of John Bell, have refuted the hidden variables theory. Here we show in a fairly simple way, how the concept of hidden variables advocated by Einstein, Podolsky and Rosen can be understood with the aid of a most common quantum device: the controlled-NOT gate.

The controlled-NOT gate (CNOT) is used to entangle and disentangle EPR states. Its unitary operator  can be written on two-bits operationally,  and , where the former is the control bit, the latter is the target bit, and  is the Galois field of two elements :

where,

The matrix  for this operation is:

	1	0	0	0
	0	1	0	0
	0	0	0	1
	0	0	1	0

Now, note that the state transformation can be replaced with , where .
In , the inverter gate corresponds to the polynomial representation , and every element satisfies the property .
Hence, the logical negation can also be represented by the polynomial .

The exclusive disjunction corresponds to the field’s addition (mod2) operation in Galois field of two elements, therefore, .
It follows that the mapping becomes for .

As quantum logic gates are reversible, the action of a CNOT gate must be undone when/if a second CNOT is applied. Hence, the transformation  must be a bijective map that is its own inverse, so that there exits the involution for .

But, the polynomial in one variable  is irreducible over , namely, it always outputs 1 for equal to 0 or 1. Therefore,  requires some hidden variable for the state transformation  to be two-way.

This is exactly the core of the EPR paradox advocated by Einstein, Podolsky and Rosen, because, if a unitary operation needs one extra piece of information outside the reach of the binary system, then the quantum theory cannot be complete.

A. DeCastro

The Walrus & the Carpenter

“The time has come,” the Walrus said, “to talk of many things…”

It’s a bumper year for mathematical related anniversaries.  Alexandre DeCastro has an upcoming post relating to a very significant anniversary we passed this May. As it’s also coming up on the 150th. year since publication of Alice’s Adventures in Wonderland and, as Dodgson was so much enamored of inverting logic, I will use him to segue my way into this review…

…I am not the walrus.

In review; the initial presentation on this blog was of a one-way trapdoor function (& PRG), the cryptographical ‘hardness’ of which is yet to be formally determined. (Tentatively termed ‘sticky predicates’, not hard nor soft, yielding yet impenetrable?)
From my remarks upon the similarities between trapdoor functions and the information preserving properties of ‘adiabatic’ reservoirs as outlined in his paper. ‘One-way-ness in the input-saving (Turing) machine‘, Alexandre DeCastro was motivated to explore this line of inquiry from a mathematical viewpoint. His distillation of the finite-field, one-way paradox was presented in; ‘A plain proof that Levin’s combinatorial function is one-way(draft)‘.
Consequently over the past year or so, we’ve presented herein, a total of three instantiations of the principle; that finite quanta or number fields yield  information paradoxes via the agency of involutionary mathematical operations. To wit; the Bennett’s paper by Alex appearing in Physica A and the mathematical exploration of Levin’s function over GF₂, along with the trapdoor-permutation by the author. You may ask, in what way is my trapdoor permutation a finite (or finitary?) construction? This goes back to the direct analogy with Alexandre’s reversible Bennett’s engine. This real numbered compression hashing represents a ‘bit-bucket’, a forward-feed reservoir of entropy arising from quantized precision overflow. As such, it iterates a temporalization of finite mathematical precision. It was Alex DeCastro’s genius to see that this quasi-involution could be distilled down to the smallest Gallois field while still retaining an anomalous dual identity.
Whilst it is long acknowledged that ZFC set theory admits paradoxes through unspecificity of power set hierarchies, the work presented here provides the first ever numerical-logic explanation for such behaviors.
Those self-same anomalies which lie at heart of the ultimate barrier to our complete understanding of the physical world, as Alex will elucidate upon in the next post.

Goo, goo, g’joob!

A Transfinite Shave

Russell’s Barber: paradox or (else) pseudoparadox?

Some axioms can be “unprovable truths” of Godel’s incompleteness theorem. Today, we show that Godel’s theorem can be easy to understand in general terms, but hard to understand beyond a typical contradiction, as per Russell’s barber (pseudo) paradox.

Consider the classical Russell’s gedankenexperiment wherein, all the men that live in a village are cleanly shaven. They either shave themselves or they do not. If they do not shave themselves, the village’s only barber must shave them.

Hence there exist two sets: the set of all men who shave themselves and the set of all men who have the barber do it for them.

But, who shaves the barber?

Let us analyze this problem based on Zermelo-Fraenkel’s set theory and Cantor’s set theory.

Zermelo-Fraenkel’s set theory

Take a male barber that lives in the village. He is clean-shaven. Then, either he shaves himself or else he does not shave himself.

Suppose the barber shaves himself. But he shaves only villagers who do not shave themselves. Therefore, the supposition is wrong.

Suppose, now, he does not shave himself. But he does shave all villagers who do not shave themselves. Therefore, this supposition is also wrong.

Hence, Russell’s gedankenexperiment is a pseudoparadox because such a barber cannot exist, since if he existed, he both shaves himself and he does not shave himself. The Zermelo–Fraenkel set theory  does not permit the barber membership of the group; “all men that live in the village”, as allowing this condition causes a contradiction which renders the theory inconsistent.

Cantor’s set theory

The disjunction “either he shaves himself or else he does not shave himself” is true if only one, but not both, of its arguments are true. We can represent such a logical operation as the exclusive disjunction X⊕NOT(X) , where X={0 = he(barber) does not shave himself, 1 = he(barber)shaves himself }.

In a finite field of two elements, X={0,1}, the inverter operation corresponds to the polynomial X+1(mod2), where the addition is computed using the mod2 operation (“exclusive or” operation), and every element X satisfies the property X²=X. Thus, the logical negation, NOT(X), can also be represented by the polynomial X²+1(mod2).

As the addition modulo (commutative) of polynomials and the XOR operation (“exclusive or” operation) are identical, X⊕NOT(X)=X⊕X²+1(mod2)=X²+X+1(mod2).

The polynomial X²+X+1(mod2) is not invertible in a finite field of two elements because it always outputs 1 for X={0,1}.

Then, either X²+1(mod2)=1 or X=1, so that X²+X+1(mod2)=1.
X²+1(mod2)=1, implies that the one-to-one correspondence NOT(X) always outputs 1 for X={0,1}, which is “false”. If X=1, then this implies that the one-to-one correspondence X(=X) always outputs 1 for X={0,1}, which is “false”.

But, X⊕X²+1(mod2)=X²+X+1(mod2)=1,  which is “true”, and, in an exclusive disjunction, the output is “true” only if one of the inputs are “true”.

Then, the exclusive disjunction “either he shaves himself or else he does not shave himself” leads to a result wherein either NOT(X) is a not invertible one-to-one correspondence or X(=X) is a not invertible one-to-one correspondence. As this result is untenable in Zermelo-Fraenkel set theory, the inference by reductio ad absurdum implies the denial of the supposition that the barber exists.

Nevertheless, the baber lives in the village, therefore, the barber is one of the group of “all men”, and, according to Cantor’s set theory, there is a one-to-one correspondence that is not invertible between the set of all men, and its powerset.

Hence, the supposition that the barber exists cannot be denied. Therefore, Russell’s gedankenexperiment leads to a paradox because  there is a true contradiction wherein the barber both shaves himself and does not shave himself.

Such a barber exists, or (else) not exists?

Alexandre de Castro

PS; I’ve changed the title from ‘infinestimal’ here as Alex points out that transfinite is in fact the correct term applicable to Cantor’s theory. I hope to expand upon matters infinestimal & transfinite as they relate to this blog in the next post… Ed.