> Cryptography rearranges power: it configures who can do what, from what. This makes cryptography an inherently political tool, and it confers on the field an intrinsically moral dimension.
Admittedly, this is true for other types of innovation as well. For example the invention of the decentralized Internet and its basic properties. Have the Internet not been decentralized, it would not have allowed folks in countries without infrastructure and money to build their own networks which are on par with the developed countries' ones. Also, free and open source software in general.
There isn't anything cryptographic in that and yet it was a big power re-arranger in a way.
Yes, i think we take it for granted by now but its obviously an invented layer and a-priory it might not have been even clear if such an architecture is workable at this scale.
The emerging picture is of a (still) wide open canvas where cryptography along with patterns like ocap models play the role of ink for drawing boundaries.
What is still unclear if all pre-existing social arrangements can be re-expressed on this new canvas and where the feedback loops between power centers and the technically skilled people will lead us.
So far the track record is not good. There are various initiatives for moral manifestos concerning digital tech here and there, but they dont seem to make much of a difference
> This construction was first made by Polish-American mathematician Stanislaw Ulam (1909-1986) in 1963 while doodling during a boring talk at a scientific meeting. While drawing a grid of lines, he decided to number the intersections according to a spiral pattern, and then began circling the numbers in the spiral that were primes. Surprisingly, the circled primes appeared to fall along a number of diagonal straight lines or, in Ulam's slightly more formal prose, it "appears to exhibit a strongly nonrandom appearance" (Stein et al. 1964).
Now, some years earlier in 1956, Arthur Clarke randomly let his imagination speculate this:
>Remarkably, noted science fiction author Arthur C. Clarke described the prime spiral in his novel The City and the Stars (1956, Ch. 6, p. 54). Clarke wrote, "Jeserac sat motionless within a whirlpool of numbers. The first thousand primes.... Jeserac was no mathematician, though sometimes he liked to believe he was. All he could do was to search among the infinite array of primes for special relationships and rules which more talented men might incorporate in general laws. He could find how numbers behaved, but he could not explain why. It was his pleasure to hack his way through the arithmetical jungle, and sometimes he discovered wonders that more skillful explorers had missed. He set up the matrix of all possible integers, and started his computer stringing the primes across its surface as beads might be arranged at the intersections of a mesh."
But Clarke never actually tried making the spiral:
> However, Clarke never actually performed this thought experiment (pers. comm. to E. Pegg Jr., May 27, 2002), thus leaving discovery of the unexpected properties of the prime spiral to Ulam seven years later.
I don’t think so, at least if you assume that each concrete solution can be expressed in finite length in a formal language with a finite alphabet, and can be mechanically checked (which is generally the case for mathematical proofs). Because then you could just enumerate all strings of that language until you find one that describes the solution to the given problem, which by your second item would be guaranteed to exist, and thus the procedure be guaranteed to terminate, contradicting your first item.
Thanks for the answer, it helps piece together the puzzle. I believe there's a problem with this reasoning:
> each concrete solution can be expressed in finite length in a formal language with a finite alphabet
Suppose that's the case, the problem is that the resulting language of all the finite proofs can still be infinite and we again cannot enumerate and check all the solutions (since the final set is infinite). Therefore we're short of a method to decide yes/no for each question.
This appears to be exactly the case in the example provided by @ykonstant
> Consider the sequence of yes/no problems P_K = {Is there a solution to Q=0 in [-K,K]^n?} parametrized by a positive integer K.
For each yes/no question, the workload is finite, but for the union of all yes/no questions, the workload is not finite.
> Suppose that's the case, the problem is that the resulting language of all the finite proofs can still be infinite and we again cannot enumerate and check all the solutions (since the final set is infinite).
The set of all strings in the language is only countably infinite (= same size as tne natural numbers), which means you will reach the solution string after a finite time (just count 1, 2, 3, ... until you reach the corresponding natural number).
What I'm saying is that if each individual problem has a solution in the form of an individual finite proof (the premise of your second point), then the above gives you a general algorithm for finding the proof for any given of those individual problems (contradicting the premise of your first point).
What this doesn't give you is a way to prove that a proof exists for all individual prohlems, because that indeed would take infinite time.
Ykonstant is correct in that your use of "undecidable" was confused; I just ignored that.
You are right, I was wrong. If there's a way to evaluate each single yes/no question in a finite number of steps, then the set of all problems is decidable, since any question can be resolved in a finite number of steps.
That would seem to imply that each problem (seen as a set of sub-problems) contains some undecidable sub-problems.. so is there something like the most primitive undecidable problem..
The way you are phrasing your question is confusing; without the parenthesis, your two statements are identical. The only meaningful way to interpret "The whole thing is undecidable" is whether you can or cannot decide all (infinitely many) statements at once.
If that is what you mean, then yes: take any undecidable Diophantine equation Q=0 of, say, n variables. Consider the sequence of yes/no problems P_K = {Is there a solution to Q=0 in [-K,K]^n?} parametrized by a positive integer K. Each of those problems is decidable in isolation, but the totality cannot be, since that would decide if Q=0 has a solution or not.
For the undecidable Diophantine equation Q=0 of n variables - I'm assuming that the fact that someone could hit a solution randomly (by randomly generating the n variables and getting lucky) does not contradict with its undecidability.
Still I'm not clear what happens if such a solution would be randomly hit for an equation that's mapped to another hard question such as ZFC consistency. It would imply that a question such as ZFC consistency could be solved by randomly generating an answer, which seemingly doesn't make sense?
