Shtetl-Optimized Open Thread
Sorry for a post-free month. I was completely preoccupied with the logistics of the move to Texas. But now that I’m finally more-or-less settled on my 1000-acre cattle ranch, with my supply of shotguns and whiskey, I’ve decided to ease myself gently back into blogging, via Shtetl-Optimized‘s first-ever SlateStarCodex-style “Open Thread.” This is not an Ask Me Anything thread. Rather, it’s a thread for you, the readers, to ask each other whatever you want or bring up any topic on your mind. I’ll chime in occasionally, and will moderate if needed. No personal attacks or local hidden variable theories, please.
Follow
Comment #1 September 2nd, 2016 at 3:07 pm
Glad you’re back, Scott!
Hello fellow SO readers,
I have a significant interest in quantum computing/quantum information theory, but not enough to go to grad school in the field. I’ve read Scott’s book, and I have a week of vaca coming up in which I plan to read a few papers like Watrous’ *Quantum Computational Complexity*, etc.
My question is: are there other amateurs out there who have found good ways of learning about quantum computing/information/complexity?
– Matt
Comment #2 September 2nd, 2016 at 3:24 pm
Thanks for opening up the discussion…
Let’s see, I don’t think this falls under “hidden variable theories”, but what are people’s thoughts about digital/finite/discrete theories of physics? Could trying to avoid the use of infinities in the math we use to describe the physical world give us any new insight? Should physicists avoid “Platonic” math ideas? Sure, using math such as calculus that leverages infinities might allow us to do certain calculations quicker and easier, but at what cost? (Maybe at no cost, if you think a little approximation here or there doesn’t hurt, or if you think the universe truly has infinities and/or continuums.)
Also, what about this nebulous term of “emergence” that is often used to describe surprising phenomenon at different levels in complex systems? Is that just a “word of the gaps” used by incomplete theories of complex systems? Or is it a scientifically justifiable term to use?
I hope these questions don’t irk the community here. I’d just like to hear some points of view.
Comment #3 September 2nd, 2016 at 4:04 pm
Is it just a co-incidence that conscienceness is at the same time the only thing we can be absolutely certain exists, and the one thing we seem to be hopelessly unable to explain?
Comment #4 September 2nd, 2016 at 4:41 pm
What about the latest rumors regarding Google’s D-wave style adiabatic quantum computing chip?
https://www.newscientist.com/article/mg23130894-000-revealed-googles-plan-for-quantum-computer-supremacy/
Comment #5 September 2nd, 2016 at 4:49 pm
In the Penrose post, you said
“Do you agree, I asked, that the physical laws relevant to the brain are encompassed by the Standard Model of elementary particles, plus Newtonian gravity?”
I’ve been trying to find a source that proves the Standard Model to be computable. The most direct source I’ve found was http://michaelnielsen.org/blog/interesting-problems-the-church-turing-deutsch-principle/ which concluded it wasn’t yet known. “On the other hand, we actually know precious little about which physical theories do (or don’t) satisfy the CTD Principle: so far as I know this problem is still open for the two leading physical theories of our time, the standard model of particle physics, and general relativity.”
The other sources I’ve found are https://arxiv.org/abs/1102.1612 and https://mathoverflow.net/questions/54820/physics-and-church-turing-thesis.
Is it still accurate to say that we don’t know if the standard model is computable, as a mathematical question?
Comment #6 September 2nd, 2016 at 5:04 pm
Are successful theoretical computer scientists capable of creating original puzzle games as compelling as Braid by Jonathan Blow? And if so, why don’t they try to do so?
Comment #7 September 2nd, 2016 at 5:25 pm
@Philip #3:
Consciousness is certainly not the one and only thing that we are hopelessly unable to explain yet. There are numerous other phenomena that are currently lacking a convincing explanation. Dark matter for example.
Comment #8 September 2nd, 2016 at 5:38 pm
Not quite a question, but if there’s some repository for “offshoots of quantum computing/information”, here’s another one for the list:
https://physics.aps.org/articles/v9/100
In short, using techniques from quantum metrology the authors device a (classical) waveguide that would allow to sense if a star is binary or not, and what the separation is, without the usual limitations of resolution.
Comment #9 September 2nd, 2016 at 6:15 pm
For the blog: It would be nice, for an open thread like this, if we could reply to an individual’s post like on SSC.
Avi (comment #5),
There is a deep and prevailing misconception among physicists and other scientists that deal with certain subtle distinctions between objects and descriptions. When we ask a question like: “Is the standard model computable?”, the question is inherently ambiguous. Are we asking: “Is every physical model that is consistent with the standard model simulatable to arbitrary accuracy with a Turing machine?” or are we asking, “Can a Turing machine capture an arbitrary amount of a given system’s dynamics?”
It may seen obvious that these two questions have the same answer, but I think we should be extremely skeptical. One of the ways that this discussion is important is in theories of hypercomputation (http://plato.stanford.edu/entries/computation-physicalsystems/#Hyp).
I personally believe that hypercomputers are perfectly compatible with the standard model meaning question 2 is answerable in the negative. That is, you cannot capture all of a hypercomputer’s dynamics with a Turing machine (by definition). However, I believe that question one can be answered in the affirmative. That is, once you have clearly specified a system, it is always possible to simulate its dynamics.
The secret come from the process of specification.
Comment #10 September 2nd, 2016 at 7:36 pm
Is there no way to reply to comments? That would make discussion much easier.
On consciousness, I am not so sure it exists. I think it’s just what happens when a sufficiently powerful computer turns it’s focus inwards.
Comment #11 September 2nd, 2016 at 7:43 pm
Majorana fermions? What is the latest news and its implications for quantum computing?
Comment #12 September 2nd, 2016 at 8:19 pm
#Matt R
Total amateur here. I found it super helpful to write a quantum computer simulator. I used Python with numpy.
Understanding is good. Simulating is better.
Comment #13 September 2nd, 2016 at 8:30 pm
R.e. #1 – there’s really no substitute for doing homework and learning some of the math.
I’m a biologist by training with a strong interest in information / complexity. Between high school and college, I received a solid math education that primarily taught me *how* to learn. I wasn’t an especially motivated math student, but I have used those foundations in calculus, set theory, geometry, and (especially) linear algebra throughout the rest of my career.
I personally discovered that I love programming – i much prefer concrete problems in discrete math over theoretical math with pencils 🙂 So, the second recommendation is to find some sort of practice that you really enjoy, and seek out puzzles or problems to solve there.
Finally, if you want to be a badass at something, do it every day for 6 months. Don’t feel too guilty if you miss a few days, but aim for 20+ minutes, 6 days a week. At the end of 6 months, you should have some sense of your own talent & continuing level of interest.
Comment #14 September 2nd, 2016 at 8:36 pm
R.e. #2 – My purely partisan opinions 🙂
” Should physicists avoid “Platonic” math ideas?”
Disagree.
“Is [emergence] just a “word of the gaps” used by incomplete theories of complex systems? Or is it a scientifically justifiable term to use?”
Very probably both.
* Like “sustainable”, “emergence” is used ambiguously, as is frequently given whatever meaning suits the individual using it.
* Nonetheless, a range of physical processes exhibit fundamentally different behaviors at different scales. I would argue that “emergence” is real, but we’re still not sure exactly what it is.
A great reference on this topic is PW Anderson’s classic 1972 paper “More is Different”.
http://www.worldscientific.com/doi/pdf/10.1142/9789812385123_others01
Comment #15 September 2nd, 2016 at 8:52 pm
R.e. #3
I take issue with the assertion that “[consciousness is] only thing we can be absolutely certain exists”. If you admit “absolute certainty” that consciousness exists, don’t you have to also admit certainty of all the observed constructs of consciousness?
If not, what is it that you’re absolutely certain of? If so, then prime numbers are just as “real” as consciousness, and basic properties of primes, like their spacing, seem about as difficult to explain as the origins of consciousness.
In short, I would argue the admittedly parsimonious position that:
* the world is big and complicated and, with very high probability, real;
* consciousness is one of many complex and difficult-to-explain real-world phenomena;
* consciousness is especially interesting to us because we’re conscious.
Comment #16 September 2nd, 2016 at 9:08 pm
Avi #5: No, I don’t know of any computability analysis that grapples with the full intricacies of the Standard Model. I think that would be great for someone to do. (There’s a reason why I phrased my response as, “do you agree…?” rather than “the following paper shows…” 🙂 )
There’s been recent progress on that issue: see in particular the paper of Jordan, Lee, and Preskill, which shows how to simulate the φ4 quantum field theory not only computably but in quantum polynomial time, as well as their extension to the fermionic case.
I think the overwhelming feeling is that the difficulties in getting from what’s been done to the full SM are technical rather than fundamental—having to do with the complexities of even defining the SM outside of perturbation theory and other limiting cases, rather than with any fundamental uncomputability in Nature itself. Or to put it another way: if someone claimed tomorrow to have a proof that the SM lets you build a Zeno computer that solves the halting problem in finite time, I think any sane physicist’s first reaction would be to look for where the SM had been pushed beyond its range of validity or an unrealistic modeling assumption was made!
Finally, even if we imagined for the sake of argument that the SM did have an uncomputable aspect, the parts of the SM that are relevant to everyday physics and chemistry, i.e. the parts that pretty much everyone besides Penrose and Hameroff consider relevant to brain function, would still be computable.
Comment #17 September 2nd, 2016 at 9:17 pm
Robert #4: The article you link to has nothing to do with D-Wave (or rather, it mentions D-Wave only to contrast it with its real subject). It’s about something extremely different, and which excites me personally a lot more: namely, the race to achieve “quantum supremacy”—i.e., a clear, inarguable quantum speedup, for a task not necessarily of any commercial use. To achieve that milestone, you don’t want a thousand qubits of debatable quality that you don’t really understand: 40-50 qubits should be enough, but they need to be of extremely high quality. As it happens, demonstrating quantum supremacy using a system of 40-50 qubits is exactly what John Martinis’s group at Google (not to be confused with D-Wave!), and several other groups around the world, are currently in a race to do. And that’s what that article was about.
My and my student’s paper, about some complexity-theoretic aspects of Martinis-style experiments, should be coming out fairly soon.
Comment #18 September 2nd, 2016 at 9:22 pm
Amir Michail #6:
Are successful theoretical computer scientists capable of creating original puzzle games as compelling as Braid by Jonathan Blow? And if so, why don’t they try to do so?
Erik Demaine has created some pretty cool puzzle games. I used to make puzzle games too when I was a kid, though I wouldn’t put mine up against anything made by professionals.
But your comment ignored the much more natural and important question: namely, are successful puzzle designers capable of proving theorems in computational complexity, as compelling as Toda’s Theorem? if so, why don’t they try to do that?
Comment #19 September 2nd, 2016 at 10:16 pm
Does quantum physics involve the universe keeping track of anything with infinite precision? If our universe is a computer simulation and quantum physics is accurate and the simulation doesn’t use any hacks or shortcuts but accurately simulates everything would this computer need either infinite processing speed or memory even if the universe is spatially finite?
Comment #20 September 2nd, 2016 at 11:11 pm
So here is what I think:
Consciousness is eternal and is not created from the brain or from matter.
There is no real thing as time, we just made it up. The present moment is eternal.
AND to top it all off, the present moment IS consciousness – they are the same thing.
I’m not going to prove this because I don’t know how, but it is what I sincerely believe from intuition, and also science hasn’t proved it false. Further it seems to make a lot of sense once you believe it.
Scientists haven’t even really been able to define consciousness or the present moment in any widely accepted way because most scientists are looking at it backwards – matter doesn’t create consciousness. Consciousness observes the universe in the eternal present moment.
It’s not mystical or anything like that, it just makes sense. Or at least it is just as reasonable as saying the big bang happened out of nothingness.
Comment #21 September 3rd, 2016 at 12:03 am
Is there any way to formalize the notion, implicit in complexity theory (and, perhaps less pervasively, in other areas of mathematics), that certain conjectures can have different probabilities of being true? Much of complexity theory revolves around conjectures that we think are true with various degrees of confidence, but are still conjectures (P != NP, P = BPP, UGC, etc.) Oftentimes, a result is important primarily because it is evidence in favor of another result being true (for example, proving that P=BPP if E requires exponential circuits). Statements of the form “The polynomial hierarchy probably doesn’t collapse to the second level” seem to make some intuitive sense. But what does “probably” really mean in this context?
I guess it means something like “Mathematicians have explored enough of the platonic realm to have the expectation it is more likely we will discover (through further processing of the theorem-proving heuristic known as the mathematical community) that PH doesn’t collapse to the second level than that it does, given our current knowledge state and associated uncertainty.” But that wasn’t a very rigorous answer.
Comment #22 September 3rd, 2016 at 12:05 am
In the area of physics and information with practical effects that sometimes comes up here, does anyone have a hot take on Unruh radiation powering EmDrives?
Comment #23 September 3rd, 2016 at 2:08 am
Scott 16, this seems confused. The question of whether the standard model is computable depends on a prior question of whether it exists. Jordan-Lee-Preskill address the complexity of the perturbation coefficients. They are obviously computable, even for the full standard model. But if you try to use them to compute the φ⁴ theory, the sum diverges. So, if that’s your definition of φ⁴ theory, I can compute it in constant time. My understanding is that φ⁴ theory doesn’t actually exist. In fact, perturbation series blow up for every quantum theory. But some theories do exist. I’m not sure about QED, but QCD is widely believed to exist. Presumably lattice gauge theory converges and so the question just becomes whether the rate of convergence is computable. Physicists almost certainly know the rate, although maybe only empirically.
Conceivably, a theory could be known to exist without its computability being known. Maybe this is the case with GR, although I am skeptical. Certainly, there are models of Newtonian mechanics which exist but are not computable. And maybe if you accept physics proofs, this is the state of QCD, but probably it is known by that standard to be computable.
Comment #24 September 3rd, 2016 at 3:47 am
What if the universe is a mind with free will?
Physicists are like somebody trying to determine the assembly language instruction set for a computer without a manual by running small software experiments and carefully determining the instruction set, which for a computer will eventually succeed.
But if the universe is a mind with libertarian free will the physicist will not succeed, the bigger mind of the universe can throw a wild curve ball the smaller mind of the physicist aided with all his computers could never predict.
I think if the universe were a computer it would it be freezing, crashing and resetting and the universe could have never grown so big.
I think the universe has to be a mind to understand what is happening and to take action to solve problems and ensure its continuing expansion.
Atheists will say there is no evidence that the universe is controlled by a mind, but we have no theory of mind and therefore there is no theoretical evidence that indicates a mind couldn’t control a universe.
Atheism or naturalism may be holding back the theory of mind and physics which incorporates mind theory.
Is naturalism holding back physics, mind theory, and angering the universe because it’s objectifying her?
Comment #25 September 3rd, 2016 at 5:39 am
Matt #1: I second Vim #12’s opinion. Write a simulator. Explaining things to a computer is a way to force yourself to understand, and a great way to catch mistakes you didn’t realize you were making.
Also, once you have your simulator, you have a useful tool for understanding papers. Instead of just reading the paper, you can ask yourself “how could I get this same result in my simulator?”, and the translation effort will give you insights into the paper.
For example, last year there was that “Quantum Pigeonhole” paper. Pop-science articles said some ridiculous things about it. The *authors* said some ridiculous things about it. So I tried to translate the paper into a quantum circuit in my toy simulator Quirk (here’s the circuit in Quirk: http://bit.ly/2bSNBKf ). Then I tried to figure out what the circuit was doing. Turns out it’s just a kind of Bell test based on the fact that a parity measurement will entangle two qubits, that your task is to reverse that parity despite not knowing which two qubits had become entangled, that rotating both qubits by 90 degrees would do the trick, and that qubits that weren’t entangled would be unaffected by that rotation so you could just hit every qubit with it.
Comment #26 September 3rd, 2016 at 5:42 am
@Scott #16
>> defining the SM outside of perturbation theory
The SM is actually ill-defined, which becomes clear at high enough energies.
But the phi^4 model suffers from the triviality problem, .i.e. a non-perturbative treatment shows that it is equivalent to a free, non-interacting theory.
So it is not clear that Preskil’s phi^4 result carries over to the SM imho.
Comment #27 September 3rd, 2016 at 6:41 am
will sha3 be broken in your lifetime?
Comment #28 September 3rd, 2016 at 8:49 am
Ben #21: Scott has tried to construct such an argument in the past, see The Scientific Case for P≠NP. That way of using Bayesian reasoning felt somewhat dubious to me, and especially less convincing than his previous take on the same subject titled Reasons to believe.
I admit that I dislike frameworks which try to reduce our state of knowledge about a given proposition to a single real number, especially Cox’s theorem, which tries to interpret Bayesian probability as a sort of unique generalization of logic.
I recently read “Die Mathematik des Daseins” by Rudolf Taschner with the subtitle “Eine kurze Geschichte der Spieltheorie”. I realized that probability theory was invented in the context of playing games, that game theory itself depends crucially on probability to represent facts like that my opponent can’t read my mind. And game semantics in logic can simplify understanding some apparent paradoxes. I wonder whether it would be a good idea to teach the basics of game theory and probability theory together, because it could help to redirect interpretation questions to fruitful questions about modeling assumptions and reasonable idealizations. And it would allow to put Bayesian reasoning into a context where its assumptions can still be reasonably judged, without forcing it into a too narrow framework (like frequentism).
Comment #29 September 3rd, 2016 at 10:06 am
The Simulation Agument
A lot of people accept that the simulation argument entails we are likely living in a simulation, including many physicists. However, many such people aren’t knowledgeable in computational complexity theory, which I think entails that we cannot be living in a simulation, and that in fact, that humanity will never reach this “posthuman” stage.
Does you think computational complexity determine which outcome is most likely in Nick Bostrom’s simulation argument? Bostrom has to basically argue for new physics that would seem to violate much of what we know in order to avoid complexity bounds that quickly grow out of control.
Quantum Foundations
Scott, no local hidden variable theories? Not even “serious” ones like ‘t Hooft’s work on QM via cellular automata? 😉
Kidding aside, I was also going to ask what people consider the most promising or interesting approaches to quantum foundations since I like reading unique and unorthodox conceptualizations of our world. Theories that are obviously already ruled out by experiment don’t apply.
For instance, the work on deriving QM from information theoretic principles looks very promising, and might yield some interesting insights. I think ‘t Hooft’s work is interesting for similar reasons, as the first serious look at superdeterminism and what is the precise character of the “global conspiracy”.
Some more fringe examples might be retrocausal-like theories, such as The Logic of Quantum Mechanics Derived from Classical General Relativity.
Another fringe example would be something like Stochastic Electrodynamics with Spin (SEDS). Their stance on Bell’s theorem and similar experiments isn’t clear, but their paper provides a firm prediction that differs from orthodox QED, so at least it’s real, falsifiable science.
There are also some interesting variations on many worlds that allegedly address some shortcomings of existing approaches.
One aspect that I always look for in an interpretation is whether it can naturally explain the source of the speedup in quantum computation, so bonus points for those!
So, anyone know of any new ideas?
Comment #30 September 3rd, 2016 at 10:08 am
Weird question: are there any instances in computer science where we have an algorithm that solves some class of problems efficiently iff such problems can be solved efficiently at all, but where we can’t prove that the class of problems can be solved efficiently?
If not, is there a reason such a scenario is impossible?
Comment #31 September 3rd, 2016 at 11:50 am
Sandro #29: My own version of the so-called simulation argument goes like this:
“If there was much more simulated habitable space than real habitable space, then it would be much more likely that we are living in a simulation than in a real world.”
However, the presumption that we should more simulated habitable space than real habitable space, is highly speculative. At this moment, we have no idea at all about the amount of resources that would be required to simulate a habitable space of a certain size. If simulations are prohibitively expensive, the whole presumption might turn out to be wrong.
Comment #32 September 3rd, 2016 at 12:00 pm
James #30: yes! There is even such an algorithm (by Levin) that solves any NP problem in polynomial time iff P=NP.
Comment #33 September 3rd, 2016 at 12:09 pm
Scott – not exactly on topic, but I’d love to know your thoughts on living in Austin (and even more what your thoughts are after doing it for six months or so, when that rolls around.)
How are the mechanics of living there? Is getting around terrible? Do you spend a lot of time in traffic (I’ve heard a few horror stories)? Are locals nice?
Comment #34 September 3rd, 2016 at 12:35 pm
Re; Jon K @ #2, “what are people’s thoughts about digital/finite/discrete theories of physics?”
My opinion, worth what you paid for it of course, is that calculus is a very useful approximation to discrete systems which have very small increments, but whether any part of this universe actually has infinite continuity is unproven. Meanwhile, every actual calculation we make in engineering or science uses discrete arithmetic, since every digital computer has a minimum floating-point value from which all other floating-point values are composed, and every analog computer, such as my old slide rule, also only uses a finite number of digits due to measurement uncertainty.
Also, we know that in discrete systems differential equations become finite-difference equations, with similar methods and types of solutions.
In engineering for example we can make calculations of girders using the differential equations of the theory of elasticity and get realistic answers, despite the fact that girders are not infinitely continuous (nor homogeneous), being composed of grains which are composed of atoms.
Finally, I think Zeno’s Paradox remains unanswered, except by discrete rather than continuous motion. I read a book whose premise was that the development of calculus answered Zeno, but it did not convince me. In calculus, the limit process is used to evaluate infinite series and infinitesimals divided by infinitesimals, so it is not necessary to physically complete the process (e.g., physically add up an infinite number of terms). That is a fine way to proceed mathematically, but I am not convinced that nature is a mathematician, and does not have to physically process all the terms.
Comment #35 September 3rd, 2016 at 1:03 pm
@Douglas #23
>> I’m not sure about QED
QED suffers from the Landau pole at very high energies.
QCD is the only part of the S.M. which seems to exist, due to asymptotic freedom, but I don’t know if the Preskill et al. result applies there …
Comment #36 September 3rd, 2016 at 1:15 pm
How much of professional math is easy? Famously, according to Barbi, Math is Hard (I couldn’t resist). And of course, CPA work, acxtuarial science, and much engineering calculation qualifies as easy. But according to Goedel, some math is not only difficult, but impossible. Recently Hamkins and Miasnikov have shown that most (but not all) Turing computable math is easy, in a well defined sense.
I think I once learned that proving even the most complicated theorem can be broken down to (many) simple steps. (Is this true?) There is also Harvey Friedman’s grand conjecture that suggests that much of Math is easy in another well defined sense. If we had an AI math reader which would read professional math journals and translate them sentence by sentence from an English like language to a fully formal language, what percentage of sentences would be easy in either the Friedman sense or the Hamkins-Miasnikov sense? What percentage of the sentences would the reader be able to translate?
Is a math logic system as good as current computer algebra systems possible? Would anyone use it?
TIA Jim Graber
Comment #37 September 3rd, 2016 at 1:15 pm
James #30: Adam #32 already beat me to it, but yes, there’s an extremely famous example of exactly that. Namely, Levin’s algorithm that attempts to find solutions to an NP-complete problem by dovetailing over all possible algorithms, halting when and only when one of them outputs a solution that checks out. This algorithm, which you could code up today, finds satisfying assignments in polynomial time iff P=NP (though with a rather impractical constant factor, to put it mildly).
Indeed, what’s surprising to me is that someone could have the thought you had abstractly, without knowing about Levin’s example!
Comment #38 September 3rd, 2016 at 1:17 pm
hi SA congrats on your dramatic move & it will be very interesting to hear about your new adventures/ exploits in this entirely new environment. was a bit stunned to hear of your move from MIT given how long youve been there, thought you might stay a long time & couldnt quite follow all your reasoning for leaving, but it was interesting to read.
this new paper by tenev/ horstemeyer caught my eye, thought it was a very cool approach & near to one have been grasping at for a long time, seems groundbreaking to me. wondering what anyone else thinks. would be interested to discuss it at length in stackexchange chat room for any takers.
https://arxiv.org/abs/1603.07655
The Mechanics of Spacetime – A Solid Mechanics Perspective on the Theory of General Relativity
SE chat room hangout/ transcripts
http://chat.stackexchange.com/rooms/9446/theory-salon
G #28: physics and math have dramatically different concepts of probability in some ways. share your initial dubiousness/skepticism on analysis of the “probability” of math problems such as P vs NP. an interesting case study is collatz which has been proven for seeds up to ~2^60 but in some ways, & strikingly, this cannot really be regarded as evidence of anything.
Comment #39 September 3rd, 2016 at 1:29 pm
@Calcott #3. Reminds me of the old saw, “If the brain were any simpler, we wouldn’t understand it; if the brain were any more complex we wouldn’t understand it.”
Understanding requires a complex brain as subject; but a complex brain as object thwarts our understanding it. We live in the sweet spot between those two extremes, I think.
The discoverability of the universe is one of those gifts that to me only makes sense because G-d created us imago dei.
Comment #40 September 3rd, 2016 at 1:31 pm
James Miller #19:
Does quantum physics involve the universe keeping track of anything with infinite precision? If our universe is a computer simulation and quantum physics is accurate and the simulation doesn’t use any hacks or shortcuts but accurately simulates everything would this computer need either infinite processing speed or memory even if the universe is spatially finite?
These are profound questions that interest me greatly—but I fear that your innocent-looking phrase “doesn’t use any hacks or shortcuts” does more work than you bargained for! E.g., what if there were an algorithm that calculated quantum transition amplitudes perfectly, but just happened to be faster and/or more space-efficient than the obvious algorithm? (Hint: depending on exactly what you mean, there are. 🙂 ) Would that count as a “hack or shortcut”?
Or more to the point: what if the algorithm promised to calculate all the amplitudes to within a precision ε>0, which can easily be made as small as desired (for example, if you could get precision ε with log(1/ε)O(1) overhead)? By your lights, is that a “hack or shortcut”? In modern theoretical computer science, we’d more often define it as just “solving the problem.”
FWIW, my own perspective is that, if you don’t think that a classical probabilistic computer “requires infinitely many bits to simulate” (because probabilities are real numbers), then you shouldn’t think that about a quantum computer either. In both cases, the key point is that the probabilities or amplitudes evolve in a norm-preserving linear way—and for that reason, no one could possibly tell the difference if they were off by some tiny ε. And even if they’re not off by some tiny ε, the mere fact that we couldn’t know even in principle if they were, makes it not too useful to think of probabilities or amplitudes as “storing an infinite number of bits.”
Comment #41 September 3rd, 2016 at 1:31 pm
Adam #32: thanks, good to know things are just as strange as they could be.
Scott #36: I’m a physicist with a maths background; weird edge cases come naturally.
Comment #42 September 3rd, 2016 at 2:28 pm
Scott, OK, I guess you mentioned said everything I said, but it seems to me that the question of whether QED exists, whether there is some number you are trying to compute, is a fundamental problem, not “technical.”
Wolfgang 35, my understanding is that the pole goes away when QED is coupled to QCD. Nor is there a pole when you add in the weak force, but it returns with the Higgs field.
Though I don’t know how much not having a pole buys you. Is it just removing an obstacle, or does it yield certainty that the model exists? Is there an actual algorithm? Does the coupled theory have asymptotic freedom?
Nor do I know how bad is a pole. My memory is that it’s not as bad as the problem with φ⁴ theory. A lot of people insist that QED really does exist. But other people agree that the pole is fatal. I’m pretty sure that no one has a method of calculation.
Comment #43 September 3rd, 2016 at 2:51 pm
This idea is known as “logical probability”, and I don’t believe anyone’s come up with a way of truly making sense of the notion. It’s something the people at MIRI have been doing a lot of work on, though.
Also, here’s an old Boaz Barak blog post on the matter.
Comment #44 September 3rd, 2016 at 3:38 pm
Related question: How much low-hanging fruit is there out there? Because I’ve managed to find more than I would have expected. Like recently I’ve been doing some work on various fairly-natural operations on ordinals — how to do computations on them in Cantor normal form, what identities and inequalities they satisfy — and there’s quite a bit of it that has been surprisingly easy, and yet, as best I can tell, just hasn’t been done before. And sure, this isn’t exactly my area, I’m not a set theorist, but I’ve done my searching (and one of my papers on this topic has been accepted for publication, so!). I don’t really know what to make of it. I recall one person suggested in response to this, well, there’s just not really a lot of set theorists. Possible, I suppose. But yeah, I don’t know what to make of it.
Comment #45 September 3rd, 2016 at 4:32 pm
@Douglas #42
>> when QED is coupled to QCD
I am not sure what you mean by that. There are strongly interacting particles which carry an electric charge as well,
but leptons (e.g. electrons) do not interact via QCD.
Comment #46 September 3rd, 2016 at 4:45 pm
Sniffnoy #44: In assessing your comment, it might be relevant for other readers to know that you have a PhD in math. So, yes, there’s plenty of low-hanging fruit in math that you can do and that’s never been done before … especially if you’re a mathematician. 🙂
Comment #47 September 3rd, 2016 at 4:50 pm
To clarify my question a little bit: Pretty much all of computer complexity theory deals with how hard a problem is and there are many layers of hardness, but I am interested in the easy problems, which in my mind occupy only the bottom most rung or possibly two on the complexity hierarchy. Or also perhaps even below that. That suggests another question: what constitutes the bottom most rung of the complexity hierarchy?
I am thinking, pretty much linear, not even polynomial.
Comment #48 September 3rd, 2016 at 5:05 pm
Andrew #33:
not exactly on topic, but I’d love to know your thoughts on living in Austin
So far, the good:
– We have a beautiful house a short walk from campus
– Colleagues and students in the CS department are great
– Lots of enthusiasm about quantum computing across campus (more than I expected); our first quantum group meetings were packed
– Even though there’s no longer Uber or Lyft in Austin, RideAustin and the other competing services seem to work just fine
– Amazing gym and pool near the CS building
The bad:
– The #1 drawback so far has been the bureaucracy of a state university. I don’t want to go into details right now, but suffice it to say: UT faculty put up with stuff that wouldn’t have been tolerated for a nanosecond at MIT. The good news, though, is that the CS department is filled with smart, sane, competent people, who do what they can to help shield the CS faculty from the university bureaucracy.
– Our first week here, it was 103-degree heat. The second week was torrential downpour. Now it’s pretty nice though, “merely” getting up into the 90s. (And of course the winter will be super mild.)
– Insects. Even though our house is brand-new, we share it with numerous cockroaches and other more exotic species. More a problem for Dana than for me though. 🙂
Comment #49 September 3rd, 2016 at 5:48 pm
James Graber #47:
what constitutes the bottom most rung of the complexity hierarchy? I am thinking, pretty much linear, not even polynomial.
You’re not thinking nearly small enough! You can go way below linear time: for starters, there’s logarithmic time, and even constant time (though such classes are very model-dependent). Then there’s NC0, where each bit of the output can depend on at most O(1) bits of the input, as well as the set of linear transformations (which are often used in place of polynomial-time reductions in algebraic complexity theory).
And if you wanted to go even smaller, well … the empty set of functions? The set containing only the identity function? 🙂
Comment #50 September 3rd, 2016 at 6:38 pm
Scott #48: “Even though there’s no longer Uber or Lyft in Austin, RideAustin and the other competing services seem to work just fine.”
An interesting take on Uber and its replacements in Austin: http://www.huffingtonpost.com/dean-baker/will-uber-go-unter_b_11396046.html
Comment #51 September 3rd, 2016 at 6:47 pm
Wolfgang, yes, but. I think you know exactly what I mean and just don’t believe me.
Comment #52 September 3rd, 2016 at 8:52 pm
Finding the 3D shape of a protein knowing only its amino acid sequence is a NP-complete problem (I think, correct me if I’m wrong) and yet a cell can figure out the correct shape in about a second. So in principle could a quantum computer do the same thing? Could the 50 qubit quantum computer Google hopes to have by the end of next year do it?
Comment #53 September 3rd, 2016 at 10:29 pm
John Clark #52: There’s a lot to unpack in what you asked!
(1) Yes, reasonable formalizations of protein-folding are NP-complete.
(2) But that fact seems to have very little to do with why protein-folding is hard for computers. Rather, it’s hard because of the large “constant-factor overhead” in simulating complicated molecules.
(3) After all, if finding the globally-optimal folding configuration required a vast combinatorial search, then Nature couldn’t do it either! Nature just blindly iterates forward the equations of physics. So if nothing else, and ignoring the constant-factor overheads, one could predict what folding configuration Nature was going to find (not necessarily the “optimal” one) by just putting those same equations onto a computer. (A quantum computer, but fine.)
(4) It’s not thought that quantum computers can solve NP-complete problems in polynomial time. (See this blog’s masthead!) Thus, if the practical difficulty of protein-folding came from its being NP-complete, then we probably couldn’t expect quantum computers to help much.
(5) OK, but as I said, the practical difficulty of protein-folding probably doesn’t come from its being NP-complete. And indeed, to whatever extent quantum effects are relevant in protein-folding, to that extent, a quantum simulation really might be expected to help.
(6) As far as I understand, it’s a matter of some dispute how relevant quantum effects really are to protein-folding dynamics. And partly because of that, we don’t really know yet how much a QC would help with the problem.
(7) In any case, unfortunately, the 40- or 50-qubit devices that the Martinis group is currently trying to build would probably be much too small to do anything with protein-folding.
(8) Having said that, it’s not absurd to think about using small, non-universal QCs for chemistry! A recent analysis by the Microsoft Quarc group concluded that ~100 qubits might already be enough to learn something new about nitrogen fixation in the Haber process, something of great importance to the fertilizer industry.
Anyway, hope that clarifies things. 🙂
Comment #54 September 4th, 2016 at 5:12 am
R.e. #52 – some biology
“Finding the 3D shape of a protein knowing only its amino acid sequence is a NP-complete problem (I think, correct me if I’m wrong) and yet a cell can figure out the correct shape in about a second.”
I worked in a protein NMR structure lab as an undergraduate. So, I’m not an expert, but have some background in this questions, and find it very interesting.
The question implies a single canonical answer, presumably based on energy minimization. This is formalized as Anfinsen’s dogma: https://en.wikipedia.org/wiki/Anfinsen's_dogma
I see this as the “algorithmic” version of the problem, which is the question that Scott presumably answered, and to which I have nothing to add 🙂
However, from the real-world systems perspective, there are two important facts to keep in mind:
* First, Anfinsen’s dogma isn’t really dogma. Of course, AA sequence is the *main* determinant of structure, but there may well be many locally stable configurations, and biological systems commonly use configurations that are not globally stable. A great example of this is prions, which are non-functionally folded proteins, where fold configuration itself is infectious: https://en.wikipedia.org/wiki/Prion
Cells deal with the folding problem in part by using chaperones. This means the folding problem depends on a network of other complex molecules, each with their own complex structure & dynamics. Also, the cell conditions can vary, including temperature to solute concentrations – sodium, chloride, calcium, magnesium, glucose, AMP, ATP, etc., an issue that Anfinsen’s dogma punts on (“at the environmental conditions”). All of these are regulated by the cell, and have some effect on the energetics of the fold, as well as the chaperone. The extent to which within-cell environmental variation affects fold energetics is an interesting question in and of itself, and could potentially shed light on homeostasic constraints (i.e., how organisms regulate their internal environment).
* Second, the *functional* structure of a protein in real-world systems is often probabilistic. The majority of biological proteins are, at least in part, in an aqueous solution at approx room temperature. In many cases, thermal vibration matters, and is critical to protein function. Case in point: in the biology literature, protein structures have historically been determined by two predominant methods: x-ray crystallography and nuclear magnetic resonance (NMR). The hard part of crystallography is growing a crystal. Once that’s done, inferring a structure is “easy” – you just x-ray it! NMR structure determination relies on the signals generated by lots of inter-nuclear interactions, and is a bit like a game of Sudoku. NMR has a critical advantage, though, in that it provides information about the structure *in solution*, which is more biologically relevant. Part of NMR’s unique information is what parts of the protein are more or less mobile, which can determine functionality.
That said, as a biologist, I’m very excited about the potential of QC in chemistry, as per Scott’s comments. Immunology in general, and vaccine design in specific, would greatly benefit from “structural computability”, even if imperfect.
Comment #55 September 4th, 2016 at 5:56 am
Are there any completeness proofs (i.e. Problem X is NP-complete) other than Cook’s Theorem that do not rely on reductions? That is, are there any known NP-complete problems that have proofs that do not rely on reductions other than SAT and 3SAT?
Comment #56 September 4th, 2016 at 6:05 am
Question(s):
I’ve been reading “Gödel’s Proof” by Nagel and Newman, which got me wondering about the formal connection between Gödel’s incompleteness theorems and Turing’s stopping problem proof. I read through your very nice PHYS771 lecture notes (http://www.scottaaronson.com/democritus/lec3.html), where you state that “once you have Turing’s results, Gödel’s results fall out for free as a bonus”.
As a non-mathematician, the proof method of “reflective recursion” (is there a better term?) appear similar between the two. Is this an over-simplification on my part, or is there, in fact, a formal correspondence between the two? Has this proof method proven useful since Turing?
Finally, is it accurate to say that Turing’s results are a generalization of Gödel’s results? I get that Turing’s results prove Gödel’s gratis, but is it fair to say that there is some sort of “injective mapping” from Gödel’s proofs to Turing’s proof?
Thanks!
Comment #57 September 4th, 2016 at 10:50 am
vzn #38: Interesting, the fact that all zeros of the zeta function computed so far had imaginary part 0.5 feels like strong evidence in favor of the Riemann hypothesis to me, which still gets stronger as more zeros get computed and checked.
But for the Collatz hypothesis, the same effort invested into checking it for specific cases doesn’t seem to carry a similar weight to me. My intuition could be wrong of course, but maybe it would be possible to identify a property of the problem itself, which explains why the fact that collatz has been proven for seeds up to ~2^60 cannot really be regarded as evidence of anything.
Even before Fermat Last Theorem was proven, the fact that it had been proven for so many n’s individually, and that the lowest n for which it was still unproven was so big, felt like very strong evidence that FLT should be true.
So if I really belief in my proposal to interpret such “logical probabilities” (as they were called by Sniffnoy #43) by replacing interpretation of probabilities by modeling assumptions and reasonable idealizations in game theory, then I should try to come up with a way to make sense of those differences in the context of that framework.
I remembered that Scott has actually tried to come with a reasonable proposal to clarify the “problem of induction” before, i.e. a way to explain its effectiveness at making correct predictions. It is in section “7 PAC-Learning and the Problem of Induction” of his Why Philosophers Should Care About Computational Complexity article, about which he also blogged. I will also have to check whether his proposal allows to make sense of those differences.
Comment #58 September 4th, 2016 at 11:56 am
Question: How advanced is complexity theory today really?
In other areas of math it took many decades to find solutions to central problems. And once found, the solutions were often not too hard to understand and teach. In set theory for example it was an open question for many years wether the first inaccessible cardinal could already be measurable. Once the right technique was invented (ultrapowers) the proof that this is not the case (and much more) was almost trivial. Or take the independence of the continuum hypothesis. Once the right technique was invented, such proofs were relatively easy. Today these things are taught in introductory courses in set theory.
Do you expect that we will see a similar thing with the open questions in complexity theory in the future? CT is still quite a young field. Is CT today where set theory was 1950? What do you think? Do you expect that someday in the future there will be a higher level machinery available, that makes proofs of P!=NP and similar assertions relatively easy such that they may even be taught in regular CS courses? Or do you expect a future proof of P!=NP will be insanely hard to understand (takes years to verify) similarly to the alleged proof of the abc conjecture?
Comment #59 September 4th, 2016 at 12:02 pm
Related to several comments: at what scale (e.g. physical length) do the Navier-Stokes equations cease to be an accurate description on fluid behavior? This is a question which can be answered by experiment.
Perhaps related: maybe the Clay Millennium prize does not ask the best/most relevant question?
Comment #60 September 4th, 2016 at 12:03 pm
@Douglas #51
Actually I am not sure what you mean, but let me try to be as clear as I can:
The S.M. consists basically of QED/electroweak , QCD and (semi)classical gravity plus the fermionic matter.
QCD is probably well-defined due to asymptotic freedom.
QED/electroweak is known to have a Landau pole.
The Landau pole could either mean that the S.M. is ill-defined at very high energy or trivial, i.e. non-interacting.
In other words, it needs a UV completion, e.g. string theory.
Of course the main motivation for string theory is that it also provides for a theory of quantum gravity. (But some think gravity may not need string theory and be “asymptotically safe”.)
In case of pure phi^4 there is good evidence that it is actually trivial/non-interacting. (It is known that phi^4 belongs to the same universality class as some well-understood lattice spin models).
Therefore it is not clear to me what the Preskill et al. result
means for the S.M. …
Comment #61 September 4th, 2016 at 2:06 pm
Christopher #55:
Are there any completeness proofs (i.e. Problem X is NP-complete) other than Cook’s Theorem that do not rely on reductions? That is, are there any known NP-complete problems that have proofs that do not rely on reductions other than SAT and 3SAT?
There’s nothing intrinsically fundamental about SAT or 3SAT. You could repeat Cook’s proof strategy, to go directly from the problem of simulating a nondeterministic TM to some other NP-complete problem of your choice. Certainly, once you know that CircuitSAT is NP-complete, it’s just as easy to go directly from there to, say, 3-Coloring being NP-complete as it is to reduce 3SAT to 3-Coloring.
The issue is just that people no longer bother to go “back to the source”—i.e., to the original definition of NP in terms of Turing machines. For once you know that 3SAT and a bunch of other combinatorial problems are NP-complete, it’s usually easier (and never harder) to start from those when giving a reduction.
Comment #62 September 4th, 2016 at 2:09 pm
JeanTate #59:
at what scale (e.g. physical length) do the Navier-Stokes equations cease to be an accurate description on fluid behavior?
See a previous Shtetl-Optimized thread, large parts of which were about just that.
Comment #63 September 4th, 2016 at 2:17 pm
Vim #12 and Craig #25: Thanks for the simulator idea! That had not occurred to me. Exactly what I am looking for
Comment #64 September 4th, 2016 at 2:20 pm
Gerald #58: I hope that someday, there’s a proof of P≠NP so simple that it can be taught in an undergrad course. But really, I’d settle for any P≠NP proof. 🙂
History renders a mixed verdict here: as you mentioned, there are many results considered hard at the time which were since simplified enormously, as the rest of the field’s language and concepts caught up with the original prover’s. (Maybe my favorite example here is Gödel’s Theorem.) Then there are other results, like Fermat’s Last Theorem, which were super-hard at the time and remain super-hard! In theoretical computer science, Dinur’s combinatorial proof of the PCP Theorem is easier than the original proof but still not a cakewalk.
I’m reminded of John Conway’s response to Bill Gasarch’s P?=NP poll: it was something like, “eventually, P≠NP will be merely a footnote in the books. It’s that we haven’t yet invented the techniques for proving computations to be hard.” That struck me as one of the most spectacularly useless statements ever made by a mathematician, right up there with “you’re lost” as the answer to “where am I?” 🙂
Comment #65 September 4th, 2016 at 4:48 pm
A hypothetical question.
Suppose God comes and says that the answer to P vs NP relies on just (really) few basic facts of algebraic, geometric and graph theory, what would be your reaction?
a) Trust the God and try to find the answer.
b) Say to God that you are not God and discard what he said
c) Decide that God does not know what he is talking about and move on
d) Ask the God for hints
Comment #66 September 4th, 2016 at 5:20 pm
I think it would be nuts if it turned out that P=NP because then it would mean (sort of) that in general writing a book is not more difficult to do than reading a book, and that can’t be right. But I do wonder why after 4 years studying it world class mathematicians still can’t decide if Mochizuki’s proof of the ABC conjecture is correct or not. Suppose I had a proof that P is not equal to NP but it would take you as much brainpower to figure out my proof as it would ignoring it and just proving it yourself from scratch. Would my “proof” really be a proof at all?
Comment #67 September 4th, 2016 at 5:33 pm
“No personal attacks or local hidden variable theories, please.”
Surely you mean to attack the idea that there already aren’t physics theories which are even more fundamental than is QM?
–Ajit
[E&OE]
Comment #68 September 4th, 2016 at 7:29 pm
Scott,
How are you feeling about the upcoming election these days?
I wish I were feeling better.
Comment #69 September 4th, 2016 at 8:52 pm
James #68: At the moment, it looks unlikely that Trump will win, but it’s super-important not to get complacent—there were also periods in 2000 when it seemed equally unlikely that Bush could win. I’ll probably do another blog post soon, asking whether we should revive the idea of NaderTrading, to arrange vote-swaps between Hillary supporters and supporters of Gary Johnson or Jill Stein.
Comment #70 September 4th, 2016 at 9:32 pm
In the 2012 presidential election Nate Silver correctly predicted how every state would go, and as of today he says Trump has a 30.9% chance of taking command of the most powerful nuclear arsenal on the planet in 137 days. That terrifies me; if I played Russian Roulette I’d only have a 16.6% chance of losing.
http://projects.fivethirtyeight.com/2016-election-forecast/?ex_cid=rrpromo#plus
Comment #71 September 4th, 2016 at 10:10 pm
Wolfgang, I claim that QED coupled to QCD just doesn’t have a Landau pole. I see nothing to elaborate on this and I think you just don’t believe me.
Also, wikipedia says that some people don’t believe that QED really has a pole and it’s just a one-loop mirage. I don’t know if the many people who don’t worry about the pole mean this or have some other reason for not worrying.
You say that the concern about a pole is that the theory would be ill-defined at high energy, as if it is well-defined at low energy. But is there any reason to believe that it is well-defined at low energy? How can you calculate low energy answers to arbitrary precision?
But there are some other issues. As a linguistic matter, I don’t think that the “standard model” includes gravity, even semiclassical gravity.
When I say that a “model” “exists” what I mean by a model is a mathematical object that has definite numerical answers. Which is obviously a prerequisite to asking whether those numbers are computable. I don’t think that semiclassical gravity is such a model. It is a human endeavor, a judgement of when to apply quantum constructions and when to apply classical constructions, and arbitrary decisions to decohere.
Comment #72 September 5th, 2016 at 1:07 am
James Graber #36:
The RO theory is that everything is easy once you know it. I tell my students this all the time. It takes a bunch of work to figure out a topic, but once you grok it, it is obvious. Calculus is a good example.
In most of math and physics, much of the work comes down to working out problems, often classic ones that define the area. In CS, it is sometimes getting programs to work. When you concentrate and wrestle with a problem, sometimes you break through and get it. Often, the breakthrough comes when you take a break. This is why so many people report conceptual breakthroughs while walking to or from (or downloading in), the bathroom. Another good reason for drinking coffee or beer while working: Faster turnaround time for BR breaks (BTW, when you knock over a coffee or beer into a key board, unplug it, take it apart, wash it, put it in the drying rack for a day, put it back together, and you are ready to go)
Comment #73 September 5th, 2016 at 5:39 am
What would be the sub-areas or problems in Artificial Intelligence which would probably lack progress currently due to not enough people working on them?
(I am asking this because AI looks to me to be an area where there could be a lot of ‘vogues’).
Comment #74 September 5th, 2016 at 8:39 am
#69
This election has brought out some of the worst elements in American politics and society. Hillary is far from perfect but it is still dismaying to me that the election looks to be as close as it appears at this time. I don’t think there will be any healing with the Trump supporters if he loses. This looks like a lose-lose situation with the craziness only getting worse no matter what the outcome.
Comment #75 September 5th, 2016 at 8:56 am
Rahul #72:
Your conscious mind first tries to find possible alternative solutions (or alternative solution strategies). Your subconscious mind is passive (not active); it works under the direction of your conscious. Finding alternative solutions thus involves loading the subconscious with the task of suggesting any relevant background or context data that carries the features of solutions.
Failure to obtain answer the straight-forward way, together with your conscious commitment to find a solution, results in the subconscious operating with a greater intensity (greater internal “tension” or “potential difference”).
The subconscious is associative. (It becomes integrative only when directed by the conscious.) The subconscious does not care so much for directionality (problem-to-intermediate steps-to solution) as for associations. If there are features that look like carrying the same initial and final states as sought, it simply throws them up all into your conscious.
If the problem has the cusp manifold topology, one of the solution pathways has a direct jump-like transition. (https://books.google.co.in/books?id=nYRMAQAAQBAJ&pg=PA54)
In your usual thought process, the nature of your conscious directions to the subconscious would be such that it would block the jump-involving solution (mainly because this solution cannot bring up all the intermediate steps).
However, the initial failure and the continued emotional commitment to solving the problem generates enough subconscious “tension” or “potential difference” that it now overcomes the usual block, and throws up the jump-involving solution too, to your conscious.
“Going away” from the problem (e.g. walking to and fro etc.) lessens the _conscious_ tension even as the tension already built into the _subconscious_ stays the same. (You have made an “emotional commitment” to finding solution.) This combination, too, further helps in overcoming the blockage to the jump-involving “crazy” solution.
When the jump-involving solution is finally gets into the conscious (overcoming the blocking potential), since there is a jump, the conscious is able to trace its route very, very fast—in a lightening fast manner. As a result, the process of discovery looks magical and also lightning fast (“Eureka”), because you are now considering only the last step.
The assumptions have been: (i) the creative problem solving process and “getting” a joke punchlines both involve the cusp manifold, (ii) there are variable levels of blocking in between the conscious and the subconscious.
–Ajit
[E&OE]
Comment #76 September 5th, 2016 at 9:28 am
John #66: “I think it would be nuts if it turned out that P=NP because then it would mean (sort of) that in general writing a book is not more difficult to do than reading a book, and that can’t be right.”
I never found this kind of argument very convincing. There are many weird and counterintuitive counterexamples in math. A P-algorithm solving SAT for example could involve solving a ramsey type combinatorial problem leading to a huge constant g (like Grahams number) and then give a running time of n^g. We would have P=NP but the algorithm would be practically unusable.
I’m in no way an expert in complexity theory and I might be wrong, but the typical example of NP-completeness-proofs I have seen, didn’t seem in any way “deep” or “sophisticated”. Most are of the type “do the obvious thing”. It’s like highschool students who construct real functions by taking out a pen and drawing lines. They would never believe a continous real function that is nowhere differentiable exists, pointing at thousands of concrete examples as “evidence”.
From looking at just the P=NP problem case alone, while P!=NP appears more natural than P=NP, I wouldn’t arrive at 99% confidence like Scott and others do. However, considering the basic open problems in CT as a whole, I expect them of to be of a similar type: We know for certain that at least some pairs of complexity classes must not be equal (NL<=P<=NP<=PSPACE, NL!=PSPACE). What would really be unexpected is P=NP by a deep nontrivial algorithm _and_ at the same time a deep nontrivial proof of P!=PSPACE (or NL!=P).
So, my personal gut feeling is that CT is not too cruel and the difficult open questions don’t come in two or more completely different and unrelated flavours: Only one deep idea should be needed to settle all the open questions (at least for the most practically relevant classes).
On abc/Mochizuki: This is different from FLT and Poincare that also required years to verify. Today apart from Mochizuki himself and one or two other people the world experts do not have yet the slightes clue how the proof is even supposed to work, not even seeing its overal structure. So, they cannot start to verify the thing and fill in the details. This looks really bad. Don’t expect a verification in the coming years.
The proof needs a serious cleanup. It should be rewritten and presented in a mostly self contained paper with all the unused generalities stripped out. Mochizuki however does not seem to want to do that.
Comment #77 September 5th, 2016 at 10:40 am
@Jon K Comment #2. if you’re interested in the view of Einstein’s position on the discontinuum vs field approaches, you might want to look at the article “The Other Einstein: Einstein Contra Field Theory” by John Statchel in Science in Context 6, 1(1993), pp. 275-290. if you (or anyone else) can’t access this article, i can send you a copy.
Comment #78 September 5th, 2016 at 11:02 am
scott: how about listing what you consider to be THE most important papers in physics and computation in the twentieth century. i assume you’ll have Turing’s 1936 paper, Einstein’s 1915 paper and Godel’s 1931 paper (and of course, Watson and Crick’s 1953 paper which is in chemistry but is relevant in many domains). don’t hesitate to include your own paper(s), if appropriate.
Comment #79 September 5th, 2016 at 11:32 am
More Questions:
I have just reread Wikipedia on Automatic Theorem Proving and Automatic Proof Checking again. Things like Mizar, Metamath, Prover9 etc. are similar to what I am asking about, only at a more powerful level. However, this has prompted me to wonder why these efforts have not been more successful, or if they (and/or other similar efforts) will be noticeably more successful in the reasonably near future?
Also, why did QED manifesto not succeed more?
(I have just discovered the recent QED + 20 special edition of JFR: https://jfr.unibo.it/ Much good reading ahead)
My previous question was on the possibility of automatic theorem proving or proof checking at an easier level which would be more predictable and more practical, but would include fail as one possible outcome. Problems include precisely defining the easier level, that pesky unreasonably large constant multiplier, and of course the percentage of fails. The reason I am optimistic is the Hamkins Miasnikov result that shows that the fail percentage can be asymptotically zero for what appears to be an important class of problems. The big question is whether this would be useful to anyone. I think “no” for automatic theorem proving, but perhaps “yes” for automatic proof checking.
Is it really known that whereas automatic theorem proving (proof finding) is clearly hard, automatic proof checking is in some sense easy or at least easier? Or is this equivalent to P=NP?
Old saw: All of math is trivial or untrue. Modern reformulation (post Goedel and post Hamkins and Miasnikov): Most Math is easy but some is hard and some is even impossibly hard.
But perhaps all the interesting math falls into that infinite asymptotic set of measure zero which is “hard”, or “impossible”.
Comment #80 September 5th, 2016 at 12:12 pm
Hi everyone!
What if I’m unable to perform arbitraty unitary transformations on qubits, and only can measure qubits form some source using polynomial set of measuring devices, perform postselection and use polynomial number of classical logical gates. Would I still be able to outperform classical computer on some tasks?
Comment #81 September 5th, 2016 at 12:47 pm
Let’s say that there exist an Oracle that will give you the correct answer for the problem instance.
What is the largest N such that we can verify the truthfulness of the Oracle?
Please provide the problem and the largest N for that problem.
Comment #82 September 5th, 2016 at 2:46 pm
#Helingstay – comment 15
I think there really is a fundamental difference between consciousness and its obseved constructs.
Consider a dream for example. Is everything in the dream real, or rather can the dreamer know that everything in his/her dream is real? Obviously not – the only thing the dreamer knows for certain is that he/she the dreamer exists – the rest might just be imaginary. Hence the conscious entity can never be absolutely sure that the “constructs of consciousness” he/she is experiencing are real.
So, yes, I stand by the statement that the only thing we know with 100% certainty is the existence of our consciousness. Our assumption of the reality of the things we observe, while reasonable and 100% neccesary for a sane existence, is not rock solid certain.
Comment #83 September 5th, 2016 at 2:46 pm
helmingstay #56: Gödel’s and Turing’s theorems are closely related but not the same thing. Historically, Gödel came first, although it “could have been” the other way around. From Turing’s theorem, Gödel’s first incompleteness theorem immediately falls out as a corollary, as explained in QCSD and many other places. The second incompleteness theorem—the one that says consistent systems can’t prove their own consistency—doesn’t fall out as easily, but can also be proved using computability arguments (see Kritchman and Raz for example). Another important strengthening of Gödel, namely Rosser’s Theorem, can also be proved using computability—see my blog post about exactly that.
Maybe the easiest way to see the connection between the two is to reflect that the “abstract core” of Gödel’s Theorem, the part that’s independent of the details of formal systems, is that there can’t be any computer program that enumerates all and only the true statements about computer programs running forever, because if such a program existed, it would solve the halting problem. The versions of the First Incompleteness Theorem for systems like PA, ZFC, etc. are then just corollaries of that fact (together with the facts that there are computer programs to enumerate the theorems of PA and ZFC, and PA and ZFC are capable of expressing statements about computer programs running forever).
Comment #84 September 5th, 2016 at 2:49 pm
Oleg #80: You haven’t specified your model in enough detail for your question to have a clear answer. But the field of measurement-based quantum computing (MBQC) is probably relevant to what you’re asking about.
Comment #85 September 5th, 2016 at 2:56 pm
James #79:
But perhaps all the interesting math falls into that infinite asymptotic set of measure zero which is “hard”, or “impossible”.
Possibly the most important skill we try to teach graduate students is to find the problems that are hard enough to be interesting, but not so hard that you can’t make progress.
(Exception: when you’re creating a whole new field ex nihilo, you get to be celebrated even for theorems that are “trivially easy” in retrospect. This is relevant if, like Cantor, Turing, or Shannon, you’re capable of creating a whole new field ex nihilo.)
Comment #86 September 5th, 2016 at 5:38 pm
#82
“Hence the conscious entity can never be absolutely sure that the “constructs of consciousness” he/she is experiencing are real.”
I am wanting to agree with you but I am not sure how you draw a distinction between consciousness and the constructs of consciousness. I would think that consciousness is composed of its constructs.
What you might be saying is we do not know how well the constructs of consciousness accurately represent the reality of some objective world that lies outside of consciousness. I think the answer to that is that it is likely they represent this objective world hardly at all or to only the extent that the representation is useful to us.
Comment #87 September 5th, 2016 at 7:09 pm
Scott, do you sometimes review comments to older posts in the moderation queue? Just wondering.
Comment #88 September 5th, 2016 at 7:23 pm
Scott #64
” Then there are other results, like Fermat’s Last Theorem, which were super-hard at the time and remain super-hard!”
Is there a science of the “hardness” of proofs?
E.g. can’t all hard proofs eventually be simplified? Are we missing some intermediate steps/tools? Is this because the techniques don’t map cleanly to the structures of the human brain?
Comment #89 September 5th, 2016 at 7:28 pm
Scott, thanks for this open thread.
By coincidence, there is a (rather long) question I wanted to ask you. (I wondered whether I should write you a short email just sketching the question and inquiring whether you would be willing to read a long fleshed out version of the question, and try to answer it. But this open thread feels like an invitation to directly ask the long fleshed out version of the question. Feel free to reply that my question feels too long or incoherent for a reasonable answer.)
I recently read a summary of a discussion between you (representing a theory of computation=TOC perspective) and people like Neel Krishnaswami (representing a Theory of Programming=TOP perspective) about computation and the (failure of the higher-order) Church-Turing thesis. That summary left me with the impression that the TOC people worry less about higher-order concepts and encoding of input, because they claim that “computation is down at the rock bottom, along with bits and integers”. But oracle Turing machines (especially the ones with an oracle for the halting problem) feel suspiciously like higher-order concepts to me. And even the encoding of integer input is non-obvious, especially if we don’t take the validity or finiteness of the input string for granted, but push the burden to reject invalid input strings including infinite strings to the Turing machine itself.
My question to you is of a slightly philosophical nature. My answer to my own question about ontological commitments of Turing machines quotes both myself (16. April ’16)
and an explanation from you (Aug 24 ’14)
Those two quotes seem to contradict each other, or at least use different notions of truth. Mine seems to use game semantics, and yours argues that arithmetic sentences have definite truth-values, i.e. allow Platonic semantics. Question: Would you argue against the conclusions from my quote, i.e. that one can accept the existence of Turing machines (including the fact that every Turing machine either halts or doesn’t halt on the empty input tape), and still reject the existence of Turing machines with access to an oracle for deciding the halting problem of a Turing machine (and be agnostic about whether every Turing machine either halts for all (finite) inputs or doesn’t halt for some inputs)?
What do you think about higher-order concepts? For example, are oracle Turing machines a higher-order concept? What is your opinion on the importance of input encoding? For example, are encodings (notations) of ordinal numbers important for ordinal analysis, or is it just important whether an ordinal is computable or not? Are block codes, bifix codes, prefix codes, and recognizable variable length codes (recognized by unambiguous finite state transducers where the only accepting state is the initial state) concepts one should know?
P.S.: The background story of my quote was not to deny Platonic truth for arithmetic sentences, but to understand the ontological commitments required for the model existence theorem, see here and here.
P.P.S.: I removed a discussion of reasonable input encodings for integers, because this comment is already too long, and the point that Turing machines are unable to reject infinite strings as invalid input is obvious anyway.
Comment #90 September 5th, 2016 at 7:30 pm
@Scott
“I’ll probably do another blog post soon, asking whether we should revive the idea of NaderTrading”
In a Facebook post Eliezer Yudkowsky suggested that if a NaderTrading-like platform were to be revived, he would want it to acknowledge that Hillary/Trump votes are worth a lot more than third-party votes*, so that each major party vote would be traded for many third-party votes. What do you this suggestion?
* Actually I don’t what was the sign of the comparison in his actual posting and don’t want to login to Facebook to check it again, but I assume he and I share enough common sense to get the same answer.
Comment #91 September 5th, 2016 at 7:32 pm
“What do you this suggestion?”
Typo. I mean “What do you think of this suggestion?”
Comment #92 September 5th, 2016 at 8:00 pm
On the topic of trying not to underestimate alien civilizations:
While participating in the Andromeda Project citizen science opportunity a few years ago, I was inspecting the high-resolution Hubble images of Andromeda for star clusters and also background galaxies when a particular image distracted me. Some constellations within it inspired a thought: Say a civilization has mapped out its galaxy in great detail and has reached a point where long-term planning on the scale of many thousands (if not millions) of years is possible. Especially if this civilization were in a spiral galaxy like Andromeda, then the disk would offer a convenient place to scrawl a leisurely message to other galaxies, via using mastery of celestial mechanics to nudge matter around and eventually shape constellations.
I have tracked down the portion of the Hubble survey containing that small section. Specifically what caught my imagination were constellations near the bottom center (definitely zoom in) of Brick 15, Field 6: https://archive.stsci.edu/pub/hlsp/phat/brick15/hlsp_phat_hst_acs-wfc_12056-m31-b15-f06_f475w-f814w_v1_rgb.jpg
Now, I make no claims you will find anything of interest or that anything in the view actually is artificial (after all, we have heard at length about the “Mars face”), yet I still find this idea of sculpted constellations (perhaps even designed to be subtle) fun to contemplate.
Comment #93 September 5th, 2016 at 9:33 pm
Scott #83: I think the reverse direction is also worth mentioning here! Hemingstay only asked about it being a one-directional thing, but since it goes both ways I think that should also be mentioned. Gödel implies Turing also because if you had a machine to solve the Halting problem, then you could apply it to a proof-searcher and conclude that everything is decidable. Unless there’s some subtlety I’m missing here.
Comment #94 September 5th, 2016 at 9:34 pm
Fred #88: As Gödel pointed out in 1936, there’s no computable function f such that every provable statement of length n has a proof of length at most f(n). I.e., there are inherent reasons to expect that even short statements can sometimes require extremely long proofs. Of course, this doesn’t say anything directly about the short statements human mathematicians might care about. But even intuitively, why would you expect that every proof humans can find, for every statement they care about, can eventually be simplified to at most 5 lines or whatever? To me, it would be way more surprising if that were always possible than if it sometimes weren’t!
(Having said that, one of the biggest determinants of the length of a proof is the level of abstraction you’re working at. E.g., I can prove Fermat’s Last Theorem in just one line if I’m allowed to cite Ribet’s theorem and the modularity theorem. 🙂 )
Comment #95 September 5th, 2016 at 9:34 pm
Itai #90: Oh geez that’s politically awful, in the sense that you’d never get people to go along with that.
Comment #96 September 5th, 2016 at 9:37 pm
Jonas #87: I review whatever I see in the queue. If I missed your comment just shoot me an email.
Comment #97 September 5th, 2016 at 9:38 pm
gentzen #89: I don’t really like that article. To my mind, computatation is fundamentally about finite strings over a finite alphabet, but that doesn’t require taking a “computation is prior to everything” view like it discusses / attributes to our host. I do math, I take the usual Platonic view ordinarily, not some formalist one. But that doesn’t in any way require admitting these other sorts of computation as “computation” in the ordinary sense.
Comment #98 September 5th, 2016 at 11:14 pm
Scott #46: Hm, you know, it’s a funny thing, I guess this could be read two ways. I was thinking of low-hanging fruit as a bad thing, as an indicator that other mathematicians haven’t done their job properly, if there’s this low-hanging fruit for me to grab. But I guess you could also consider it as a good thing, if you want to find something easy to solve! (Say, to make a name for yourself.) Given that I don’t actually have an academic job at the moment and am hoping to break back in, perhaps I should consider it as the latter. 😛
…I was going to go for particular examples here, saying “I don’t think you even need a PhD in mathematics for such-and-so, they’re even lower-hanging than that”, but that seems like the sort of thing that would lead to unrpoductive arguments, so uh I think I’ll just skip that…
Comment #99 September 5th, 2016 at 11:54 pm
Two TCS StackExchange questions that pursue this intuition are “Are runtime bounds in P decidable? (answer: no)” and “Do the undecidable attributes of P pose an obstruction to deciding P versus NP? (answer: maybe)”; there is also a TCS community wiki associated to the question “Does P contain languages whose existence is independent of PA or ZFC? ”
As the StackExchange’s diverse answers, comments, and literature references show, opinions differ pretty widely in regard to the merits (or lack of merits) of this class of “higher-order” complexity-theory questions. To the extent that there is any consensus at all, it’s along the lines “Our present understanding of complexity theory is not adequate to provide illuminating answers to this class of questions.”
Comment #100 September 6th, 2016 at 12:53 am
I happen to think that mathematics is overflowing with ‘low-hanging fruit’ in the form of beautiful and relatively easy questions that no one has thought of asking yet. Some amount of creativity can sometimes go further than the same amount of problem-solving genius. Of course, if no one else has considered the question it can be more difficult to convince anyone that it’s worth answering.
Comment #101 September 6th, 2016 at 3:03 am
Scott, I’d be curious to hear your thoughts (if any), on this paper from Mehta and Schwab on deep learning and the renormalization group:
http://arxiv.org/abs/1410.3831
The mathematical correspondence they define is a perhaps trivial and probably doesn’t hold for many deep learning networks that have saturating nonlinearities, but it still seems that the vast RG literature might contain some insights useful for deep learning theory…
Comment #102 September 6th, 2016 at 5:00 am
@Scott #69
>> NaderTrader
Is vote-swapping legal?
You cannot sell your vote, so how can trading votes be legal?
Obviously you try to undermine/circumvent the electoral system as envisioned by the Founding fathers …
Comment #103 September 6th, 2016 at 7:48 am
Sanjeev Arora, Moritz Hardt, and Nisheeth Vishnoi are the proprietors of a lucid and enjoyable weblog Off the Convex Path (OTCP), whose computational objectives overlap very substantially with the objectives of renormalization group methods:
Such reflections give rise to (the three most recent OTCP posts) “Markov chains through the lens of dynamical systems: the case of evolution” (Nisheeth Vishnoi, April 4, 2016), “A framework for analysing non-convex optimization” (Sanjeev Arora and Tengyu Ma, May 8, 2016), and “Linear algebraic structure of word meanings” (Sanjeev Arora, July 10, 2016).
As Huckleberry Finn said of John Bunyan’s The Pilgrim’s Progress from This World to That Which Is to Come; Delivered under the Similitude of a Dream (1678), “The statements was interesting, but tough“.
Shtetl Optimized readers, in particular, can enjoyably precondition their appreciation of these three essays by the replacement
\(\text{Darwinian evolution}\to\text{Lindbladian evolution}\)
As Vishnoi remarks of the former dynamics, so too of the latter dynamics: these are Nature’s dynamical algorithms, and hence heuristically are deserving of our particular attention.
Terry Tao’s essay “What is good mathematics?” (Bull AMS 2007, arXiv:math/0702396) enumerates 21 traits of good mathematics.
Tao’s essay emphasizes that any such listing necessarily is incomplete, and sure enough, the OTCP essays present a 22nd trait of good mathematics: hilarity.
As a concrete example of mathematical hilarity, I have in mind the first sentence returned by the algorithm of the OTCP essay “Linear algebraic structure of word meanings” in searching for usages of the word ring:
When we seek to extend the OTCP’s computational themes to the domain of quantum simulation, such statements are very commonly encountered — Joe Harris’ and David Eisenbud’s just-released and much-praised 3264 and All That: A Second Course in Algebraic Geometry (2016) is replete with them — and the hilarious point is that it isn’t only OTCP’s deep-learning algorithms that find such statements to be (in Huck’s phrase) “interesting but tough”. 🙂
Here as in very many STEAM-domains, neither human understanding nor computer algorithms are all that close to achieving “a thorough conceptual understanding of what’s going on.” Fortunately, we can see clearly enough to be entirely confident that unifications of our understanding are both possible and natural: unifications that embody all 21 of Terry Tao’s traits of good mathematics … and hilarity too.
Comment #104 September 6th, 2016 at 10:25 am
Sniffnoy #97: Wow, you seem to be an expert on encoding of integers who has worked with people like Jeffrey C. Lagarias and Andreas Blass. You also did some work on various fairly-natural operations on ordinals. I would like to ask you a serious question about encoding of integers:
What do you think of straight-line program encodings? Here in addition to 1’s, additions and multiplications (which are used to define the integer complexity), you are also allowed to use variables. (It is basically equivalent to the arithmetic circuit representation.) You probably know Haskell. There you can easily end up with a number temporarily stored in that representation, especially if you produce a space leak by thinking too “imperative” and not evaluate in the appropriate order. Some operations like comparison (both equality and greater than) become challenging in that representation, but other operations can be executed much faster.
Do you think that this is a reasonable encoding of integers? Or is it at least not less reasonable than the unary encoding of integers? How would you rate it compared to the binary encoding of integers?
Comment #105 September 6th, 2016 at 1:00 pm
gentzen #89: I don’t even understand what it would mean to “reject the existence of a Turing machine” (with or without an oracle for HALT). Since TMs with HALT oracles can be put in 1-1 correspondence with the positive integers, it seems almost exactly like rejecting the existence of some positive integer. Or do you mean to deny that there’s a definite fact of the matter about whether a TM with HALT oracle halts or not? Well then, why not deny that there’s a definite fact of the matter about whether an ordinary TM halts or not? After all, the former kind of fact is “built out of” the latter kind.
Regarding input encodings, what theoretical computer scientists really have is a pragmatic attitude: they worry about encoding details when they matter for whatever question they’re trying to answer, and not when they don’t. Most of the time (e.g. unless you’re worried about constant factors and things like that), it’s perfectly fine to work at a higher level of abstraction where low-level encoding details don’t matter.
Which, yes, theoretical computer scientists are perfectly happy to do, and do all the time, and wouldn’t get far if they didn’t do! But the possibility and usefulness of higher-level abstractions in no way calls into question the validity of the Church-Turing Thesis, or the fact that computation is ultimately defined in terms of strings of 1s and 0s. These facts are not only consistent but deeply harmonious with each other. That was my point in the other thread.
Comment #106 September 6th, 2016 at 1:05 pm
wolfgang #102: Absolutely not! You’re out of date (as indeed I was, until this week). In 2007, the 9th Circuit Court of Appeals explicitly ruled vote-swapping to be legal, and indeed protected by the First Amendment. See here and here.
Comment #107 September 6th, 2016 at 1:34 pm
Scott # 85
“Possibly the most important skill we try to teach graduate students is to find the problems that are hard enough to be interesting, but not so hard that you can’t make progress.”
How do you but do that? (Not the judging process, which obviously cannot be formulated in a blog’s comment section, but how do you TEACH to do the judging.)
Comment #108 September 6th, 2016 at 1:50 pm
@Scott #106
I see, well then you can indeed help Trump by encouraging people swap their Gary Johnson votes 😎
Comment #109 September 6th, 2016 at 6:52 pm
Scott,
Do you have any opinion on analog-computation and differential equation based SAT-solvers.
Theory:https://arxiv.org/abs/1208.0526
Recent preprint on experiment ‘Efficient Analog Circuits for Boolean Satisfiability’ :http://arxiv.org/pdf/1606.07467.pdf
Comment #110 September 6th, 2016 at 7:26 pm
Anybody else here a college drop-out?
Comment #111 September 6th, 2016 at 7:40 pm
Scott #106: Wow! Thanks for the link to the decision — and it’s good to know that this has already been through a federal appeals wringer. Though it sure is Napster-flavored, isn’t it? And I’m not persuaded that it’d find the same reception at the Supreme Court level, where I imagine the question will have to have to go at some point.
Comment #112 September 6th, 2016 at 9:08 pm
gentzen #104:
…OK, please don’t do this.
Like, look around you. (Not literally.) You’re commenting on a blog run by Scott Aaronson. Regular commenters here have included a number of well-known mathematicians and computer scientists. It’s really a bit embarrassing to have someone go all “Wow!” over me due to other mathematicians I have some association with, when, like, plenty of well-known mathematicians and computer scientists are right here.
I mean, I’m not going to knock my work, I think it’s pretty great, honestly! (Even if some of it is a bit LHF.) But like, really man, that’s just embarrassing. Like, really… in a place where mathematicians are hanging around, it’s not going to be my association with well-known mathematicians that’s noteworthy. I mean… mathematics just doesn’t seem to be that large a world, you know? And I went to University of Michigan, so, like, that’s even less surprising.
(Also, I have not worked with Andreas Blass to any real extent. He was second reader on my thesis, and he’s occasionally pointed me towards useful set theory references. That’s mostly it.)
You want to gush over my work, go ahead, I for one think it deserves it. 🙂 But, like, this is embarrassing, man.
As for your substantial question… I’ll answer that in a separate comment.
Comment #113 September 6th, 2016 at 9:51 pm
Hey Scott,
I read your position on the Chinese Room problem and thought of asking you a related question: if we accept that passing the Turing Test is a good criterion to tell if a test subject has something of a consciousness of the kind humans possess, then how do you propose to pass a Turing Test designed, say, in Pashto, or about topics in which you have little understanding?
And if you don’t pass such a Turing Test (which will be passed by a Pashtun villager, e.g.), would it not mean that we need to qualify what we think we understand about what passing the test really means?
For example, shouldn’t passing the Turing Test strictly mean that the test subject exhibits a kind of intelligence consistent with the control subject(s)?
I would like to know your thoughts on this and other related issues that you believe this gives rise to. 🙂
Comment #114 September 6th, 2016 at 10:03 pm
I’m familiar with straight-line programs. You’ll notice I’ve done some work on addition chains, which are straight-line programs with only addition allowed! (And I have some speculation about what analogues of my theorems and conjectures might hold when multiplication or subtraction is also allowed, but these are, as I said, speculation.)
I do not think it makes sense to consider these as “encodings” of natural numbers, for a number of reasons. Our usual encodings of natural numbers are either base-b for some b or slight variations on it (e.g. bijective base-b). Because, these work really well! Let’s just take ordinary binary to be concrete. What are some good features of binary?
1. Every number has a unique binary representation (again I am only considering natural numbers here)
2. It’s easy to write down algorithms for how to add two binary numbers, for how to multiply them, for how to compare them… etc. (I guess testing for 0 and taking predecessors are important ones, too, so you can write recursions.)
Given this, it’s unclear why you’d want to represent natural numbers with something like a straight-line program.
Say we want to encode the elements of a set A via elements of a set B; let’s consider this as a map from B to A. The best possible case is that this is a bijection from the B to A (as we have with binary above). Failing that, hopefully at least we can get a “canonical form” map going the other way, back from A to B, that we can easily compute. (And then we can say that the real encoding is given by restricting B to the image of the canonical form map.) And if even that fails, well, hopefully we can at least, given two elements of B, check whether they yield the same element of A.
Binary does great here, as I’ve said. Straight-line programs? Yikes. You’ll have many straight-line programs for one number. None seems particularly canonical. And I guess checking equality is quick in that you can compute the actual number (in binary), but that just raises the question of why you aren’t just using binary.
As for standard operations… OK, I guess you can add and multiply — and if you allow subtraction, subtract and take predecessors — in a trivial fashion, but… how do you compare? How do you compare to 0, in particular? By resorting to binary, it would seem. Again: Why bother with this? Just use binary.
I really do not understand why you would want to ever consider this as an encoding of natural numbers. (Although there is apparently some reason that a number of people come to, as for whatever reason a number of people have suggested something like this to me. Most of those people were not mathematicians, though.) Binary is good. I suggest using it.
Comment #115 September 7th, 2016 at 12:26 am
Is there any classical public key crypto system that is unbreakable by the quantum computer? I know there are some lattice based systems but could they remain safe in the future?
Comment #116 September 7th, 2016 at 6:34 am
Unraveling the functional dynamical properties of molecular and condensed matter structures — classical, quantum, and hybrid — is the core business of the computational simulation company Schrödinger LLC, and at least some Shtetl Optimized readers may wish to acquaint themselves with Schrödinger’s simulation suites and peruse the numerous job openings for scientists and engineers that Schrödinger presently is advertising.
As the dynamicist Vladimir Arnol’d has said, “Mathematics is the part of physics where experiments are cheap,” and nowadays this is no joke, but rather a concrete reality of experimental physics and chemistry. In particular, it won’t be easy for Google’s advances in dynamical simulation with quantum computers to exceed the pace of Schrödinger’s advances in dynamical simulation with classical computers.
Needless to say, our mathematical understanding of computational simulation algorithms benefits greatly from the work of both companies. Indeed, it is entirely likely (as it seems to me) that sustained advances in simulation capacity by either company will greatly benefit the other company too.
Comment #117 September 7th, 2016 at 9:38 am
Jiayu #115: Yes, there are the lattice-based systems (and closely-related LWE-based systems, etc). No one knows if they’re truly safe against QC, just like no one knows if RSA and Diffie-Hellman are secure against classical computers. In both cases, though, they haven’t been broken yet.
Comment #118 September 7th, 2016 at 9:43 am
Arko #113: The usual view that’s defended is that passing the Turing Test is sufficient for us to want to ascribe thinking to something, but not necessary. There are all sorts of reasons why a thinking being might fail the TT, including not speaking the language (as you said), being asleep or incapacitated, not wanting to participate, being an alien form of intelligence, etc. But at any rate, it seems extremely unlikely that any non-thinking being would pass a strong TT. (The adjective “strong” is crucial in the previous sentence! Still, of course, some people dispute this view.)
Comment #119 September 7th, 2016 at 10:08 am
My primary mathematical motivation to “reject the existence of …” in the context I quoted was to understand the “minimal” ontological commitments required to prove the model existence theorem. The syntactic strings were fine for me, but I was unsure about the equivalence relation on them, which is constructed in (the Henkin style proof of) the theorem. I guessed it would be easiest for me to understand it in terms of (oracle) Turing machines. The first realization is that I have to accept the existence of Turing machines and that there’s a definite fact of the matter about whether a TM halts on the empty input tape or not. Otherwise, I cannot even talk about consistency at all.
Now comes the surprise: The construction of the equivalence relation requires an oracle TM, and the constructed model can itself be seen as an oracle. However, even if we put in the true oracle for HALT, the resulting oracle (i.e. the constructed model) will not be the true oracle for HALT. But even more surprisingly, the model existence theorem doesn’t really need the true oracle for HALT, any plausible oracle (see below) will do. For the normal Henkin style proof, that oracle has to think/claim that the given axioms (for which we want to construct a model) are consistent, but Noah Schweber showed that Rosser’s trick can be used to modify the proof such that even this is not required, as long as the oracle is plausible (and he rigorously defined that notion too).
OK, I guess you have heard this “we neither need it, nor is it preserved under …, hence we don’t want to assume that it always exists” attitude before. Even if you would accept that attitude towards existence, you could cite the Shoenfield’s absoluteness theorem as evidence that it is preserved in the relevant contexts. But my guess is that you basically reject that attitude to define existence based on such utilitaristic considerations. Still, I hope it became clear what it would mean to “reject the existence of a Turing machine” (with or without an oracle for HALT).
Now that I hopefully clarified things, let me link to Quine’s On What There Is for some good reasons to reject “being of possibles (and universals)”, and the slogan “To be is to be the value of a variable” to sum up the criterion of ontological commitment. Finally, here are three different passages I wrote, which convey some feeling what it means for me personally to accept or reject the existence of idealized constructs:
Comment #120 September 7th, 2016 at 11:09 am
In thinking on the wonderfully meta #66 I wonder what the implications would be of discovering a proof that P!=NP vs P=NP is undecidable. I’ve read accounts of what we’d learn and all the things that would fall out if we had a proof either way, but what if we had proof that the question can not be decided and can only be decided by putting it in as axiom?
Comment #121 September 7th, 2016 at 11:22 am
RE: election
I’m generally of the belief that we should make good faith effort to understand those we disagree with and to hear them out. To try and steel man their arguments and not shy away from facts and arguments that are difficult to reconcile with our own beliefs.
I’m highly skeptical of ridiculing the other side as dumb and unintelligent or somehow not possessed of the ability to assess their own self-interest. This strikes me as patronizing and condescending and often the lazy way of dealing with arguments that make us uncomfortable.
But DAMN am I having a hard time with this election! I think I have understood the other side and just find them utterly wanting and mired in base delusions at best and sheer stupidity/ignorance at worst. And then I look at many ostensibly on my side of the aisle and find all kinds of ill behavior and shoddy thinking.
Thank goodness this election is almost over one way or another and we’ll have our answer. I do confess that my opinion of many people who vote the *wrong* way is likely going to take a hard tumble.
What do you do when you engage in good faith and steel man their arguments and still find that a too large percentage of your fellow man is just so base wrong?
Comment #122 September 7th, 2016 at 12:28 pm
Helingstay #14:
Thanks for the response and that article. So maybe it is your belief that we need to develop and employ lots of different types of mathematics depending on the level and phenomena we are interested in analyzing? In your opinion, is there any hope for a “grand unified theory” in physics?
JimV #34:
I totally agree with you on Zeno’s paradox, and pretty much everything else you wrote. So do you think there is any benefit in exploring “digital physics” models where discrete, system phenomena can be approximated using continuous mathematics (or floating point approximations of continuous models)? Obviously, “digital physics” models would fit in nicely with simulation theories, but do you think looking at the physical world from a discrete and finite perspective might offer any additional insights?
Richard G #77:
I was aware of Einstein’s skeptical views towards continuous field theories because I actually used a quote of his to promote my movie “Digital Physics”, but I haven’t read that paper you referenced before. I was only able to get a slide deck pdf on the topic from a presentation John Stachel gave at the Perimeter Institute, but not the paper itself. How can I get a copy? Thanks!
Comment #123 September 7th, 2016 at 12:28 pm
Scott #69: Democrats+Republican vote swapping in favor of Gary Johnson (Libertarian Party) is available here:
http://balancedrebellion.com/
Comment #124 September 7th, 2016 at 2:42 pm
Michael #123: No, that’s completely different from vote-swapping as I understand it.
Vote-swapping:
Johnson supporter in swing state votes Clinton
Clinton supporter in safe state votes Johnson
This thing:
Clinton and Trump supporter in swing state both vote Johnson
Not surprisingly, this other thing is being advocated by Johnson supporters. 🙂
Comment #125 September 7th, 2016 at 4:11 pm
@Scott #124
I think your kind of vote swapping is a nice academic idea which made some sense in 2000, but in 2016 the issue is way too emotional imho.
A #NeverTrump conservative who votes Johnson because she is disgusted with Trump will not vote-swap in your sense, because she does not want to vote Trump after all.
The same is true for BernieBros who are disgusted with Hillary and go for Gary or Jill instead.
I think in 2016 Michael’s link is much more appropriate: Voters who do not want to chose between wtf-man and liar-lady can agree to vote for Gary or Jill instead.
ps: Full disclosure, I am not a US citizen and do not have to make that choice.
Comment #126 September 7th, 2016 at 5:14 pm
I have a question about Scott’s paper on Closed Timelike Curves with John Watrous.
In section 2.1 they define a function M with a fixed point that, if you find it, solves an NP-hard (or PSPACE-hard, whatever — something hard) problem. I’m wondering why M needs to set up that looping behavior. Could it just as well be M(x) = x if x is a solution to the hard problem and M(x) = 0 (or M(x) = 666 or -x or whatever) otherwise?
Maybe it seems like the solution is, in a sense, more out of the blue that way but, like they say in the paper, “a rough analogy would be Shakespeare’s plays being written by someone from the present going back in time and dictating the plays to him.”
(This question brought to you by debating a scene in Harry Potter and the Methods of Rationality.)
Comment #127 September 7th, 2016 at 5:37 pm
This question is a subset of a broader MathOverflow question, to which numerous mathematical luminaries have contributed, “For which Millennium Problems does undecidable -> true?”
The consensus answer for PvsNP is “not obviously”.
Note also that the Clay Institute’s prize jury reserves the right to amend any and all of the Millennium Prize questions as required to recognize outstanding answers. Thus it’s entirely consonant with the intent of the Millennium Prizes, to amend the traditional definitions of the complexity classes P and NP, provided that such amendments are consonant with any or all of the diverse traits that Terry Tao (for one) has identified as as characteristic of good mathematics (see arXiv:math/0702396).
Don’t like oracles? Then show that complexity theory becomes more interesting without oracles than with them. Sounds goofy, but on the other hand, algebraic geometry was transformed in the latter half of the 21st century by radical redefinitions in the consensus view of “what algebraic geometry is about.”
Are comparably radical transformations in store for 21st century complexity theory and/or quantum computation theory? Shtetl Optimized surely would be a far less interesting blog if the answers to these questions were obvious! 🙂
Kudos to Scott for his suggestion that good Shtetl Optimized questions commonly make good StackExchange questions.
Comment #128 September 7th, 2016 at 7:40 pm
Phil #101:
Thx for the intriguing link. In case you didn’t see it, below two related ones:
https://charlesmartin14.wordpress.com/2015/04/01/why-deep-learning-works-ii-the-renormalization-group/
http://lesswrong.com/lw/ld4/link_an_exact_mapping_between_the_variational/
Comment #129 September 7th, 2016 at 7:52 pm
Jon K. #122 (and #2),
I urge you and those who responded to your comment to give some close attention to the following paper from 2004:
“Quantum general relativity and the classification of smooth manifolds” (Hendryk Pfeiffer)
http://arxiv.org/abs/gr-qc/0404088
From the abstract:
“In any dimension d<=5+1, the classification results provide us with triangulations of space-time which are not merely approximations nor introduce any physical cut-off, but which rather capture the full information about smooth manifolds up to diffeomorphism."
From the body of the paper:
"If quantum general relativity in d = 3+1 is indeed a PL-QFT, the following two statements which sound philosophically completely contrary,
• Nature is fundamentally smooth.
• Nature is fundamentally discrete.
are just two different points of view on the same underlying mathematical structure: equivalence classes of smooth manifolds up to diffeomorphism."
I think this is a very important insight, and may have wide-ranging and profound ramifications for physics, and for sorting out the deep difficulties of quantum gravity in particular. As far as I know the paper has been largely ignored.
Comment #130 September 7th, 2016 at 7:57 pm
PS: Hendryk Pfeiffer is currently at the University of British Columbia. See his LinkedIn profile.
Comment #131 September 7th, 2016 at 8:15 pm
Another PS: Also see the paper hep-th/0307247, submitted to arXiv.org by Pfeiffer’s co-author in 2003. From the abstract:
“.. … .. An important lesson beyond string theory is that a fundamental length scale can be implemented into the kinematics of general relativity, whilst preserving both space-time as a smooth manifold and local Lorentz symmetry, contrary to common belief. .. …”
From the opening paragraph of the paper:
“The preservation of Lorentz invariance is crucial, as this is one of the most accurately tested symmetries in physics, with no indication that it is broken or deformed at any observable energy scale.”
Comment #132 September 7th, 2016 at 8:18 pm
Sniffnoy #112: Sorry, but going gush is so much fun. After Scott warned that you have a PhD in math, I tried to find out who you are, and mainly communicated the fact that I have done so. But I really was delighted to see …
Sniffnoy #114: If I were forced to convert the straight-line program encoding to binary to do equality checking, then it would indeed feel strange to consider this as an encoding of natural numbers. But I can do efficient probabilistic equality checking by drawing some number (in a suitable range) and do the computation modulo that number. Whether the greater than operator can be evaluated efficiently in a suitable sense is less obvious.
I can do more than just add and multiply with this encoding. I can take the exponent with an integer encoded as addition chain. And the fact that I’ll have many straight-line programs for one number where none seems particularly canonical is precisely the reason why I want this encoding: As a counterexample to the widespread belief that equality checking for integers is trivial independent of the encoding.
The reason why I came up with this encoding in the first place was NJ Wildbergers style of ultra-finitism, which depends on such complexity theoretic questions. It is less relevant to my question to Scott about higher-order concepts and importance of input encoding. (Maybe I will post my removed discussion of reasonable input encodings for integers later, to clarify the sort of issues I suspect there.)
Comment #133 September 7th, 2016 at 8:26 pm
Re #77 and #122,
The DOI link for John Stachel’s “The Other Einstein: Einstein Contra Field Theory” is:
http://dx.doi.org/10.1017/S0269889700001381
Comment #134 September 7th, 2016 at 8:33 pm
Also, in the citations at http://philpapers.org/rec/STATOE, I came across http://philpapers.org/rec/HAGLMT:
Comment #135 September 7th, 2016 at 10:03 pm
This seems like a good place to ask this: I’m going to be teaching an “Exploration” class for a short January term on cryptography and its history. The class is aimed at students who have precalculus but not necessarily any other math background. Do people have suggestions for topics to cover or specific reading that might be good? Right now, I’m planning on starting with ancient systems like substitution ciphers, through later polyalphabetic ciphers, and then looking at Diffie-Hellman, and RSA and related ideas. Along the way I’m intending to look at the historical and policy questions that arise. What other topics would people recommend I cover?
Comment #136 September 7th, 2016 at 10:04 pm
Scott #118: The way you use the adjective “strong” sounds as if it should be “strong” with respect to the control subject. In which case one has to design the Turing Test with knowledge about the control subject. Does that not kind of defeat the purpose? It appears that the only way one can design a “strong” Turing Test is if one has an a priori understanding/knowledge of the test taker.
E.g., I could design a Turing Test for you in English, but about a set of topics that you are very little aware of.
Also, I see a bit of circularity in your response: on one hand, we would call a being possessing thinking capabilities if it passes a Turing Test, on the other hand we are saying it would pass a Turing Test if it possesses thinking capabilities.
Comment #137 September 8th, 2016 at 2:44 am
gentzen #132: I’m not hidden. Using Google is not particularly noteworthy. And again, there are plenty of mathematicians here.
As for straight-line programming considered as an encoding… this all just sounds deliberately perverse. Probabilistic equality checking? Yikes! And your suggestion for exponentiation only works if the exponent is given as an addition chain — OK, you made a note of that point, but like, that’s actually a serious deficiency, if certain representations don’t work as inputs (or first have to be converted to a specific form in a potentially costly manner). Anyway, the most important thing about the natural numbers is the ability to write recursions. That’s kind of the defining property, really. You have to be able to do predecessor and comparison to zero or it’s not a good encoding, IMO.
(By the way, I would dispute the statement that I am an “expert on encoding of integers”. What I have studied is (particular aspects of) the computation of integers in weak computational models. As I’m arguing here, I do not think that should be considered “encoding of integers”.)
And I mean, you basically confirm this:
So you are, in fact, looking for a deliberately perverse encoding. OK. Now, that would be something if it were to serve as a counterexaple to some actual mathematical statement, but instead it’s supposed to serve as a counterexample to “widespread belief that equality checking for integers is trivial independent of the encoding”.
Which… huh? I mean, OK, maybe there are people out there who believe this, I don’t do foundations, but like… this seems obviously false? I mean first of all this doesn’t even seem like a formal mathematical statement. And like for this to be true — what properties of the integers could this possibly rely on? Thing is, this statement is making use of none of the structure of the integers, just considering it as a set, so how could anything special about the integers possibly have any bearing on it?
But like it should be much easier than you’ve suggested to come up with perverse encodings that make deciding equality hard. Here’s one for you: Encode n as a finite graph with chromatic number n. I’m really not clear on in what way there is even supposed to be a problem here, and without an actual mathematical statement you’re trying to disprove I think you’re going to have a hard time convincing me there is one.
Comment #138 September 8th, 2016 at 2:53 am
I could fairly easily write an addon you the reader of this blog could install which would automatically turn text like “Scott #7” in existing comments into a link to the comment in question, and add a ‘reply’ link to each comment which would give you an inline reply box pre-populated with such a link.
With a little more effort I could make it such that hovering over such a link would give you a floating box with the comment in question, 4chan-style (link SFW).
With much more effort I could automatically rearrange comments into a tree based on post times and which comment they are replying to (assuming they either use the proposed link or the local convention of starting with “Scott #7” or similar). It’d make page loads a little slower, especially if they had a lot of comments, but it would make threads much easier to follow. (This wouldn’t work perfectly, because sometimes people address multiple comments and the graph is therefore a DAG (assuming you don’t manage to reference comments after yours, in which case it’s just a graph), which is trickier to represent.)
Would there be interest in such a thing? I could make it as a browser extension with no support from Scott. It would probably make more sense for Scott to do most of this by changing the WordPress config, of course.
For reference, I wrote a similar addon script for SSC’s comment system, which is now just included in the site. (It’s what marks comments as unread and lets you collapse them and so on.)
Comment #139 September 8th, 2016 at 6:18 am
@#135
” The class is aimed at students who have precalculus but not necessarily any other math background. ”
I helped design and teach an undergraduate, no-prerequisites class titled “Probability for Scientists” at the University of New Mexico in 2013.
We got a lot of mileage from hands-on exercises designed as games, typically with dice and/or coins, to provide concrete examples of randomness, sample space, etc.
I imagine that information entropy is a critical topic for you. The classic game of identifying human-generated versus true random numbers provides a great intro to “what is randomness” (and why are humans so bad at generating it)? If you address issues of security and side-channel attacks, you could also refer back to humans’ predictability wrt password generation.
Here’s the course website for that exercise:
http://probforsci.blogspot.com/search/label/Week%201
Also, for broad or intro-level courses, I’ve had good results from including episodes from professionally produced youtube instructional content, things like Crash Course Biology. For cryptography, Art of the Problem has a great series titled “Gambling with Secrets” that is really well produced: https://www.youtube.com/watch?v=lICOtR078Gw&index=1&list=PLB4D701646DAF0817
-hth
Comment #140 September 8th, 2016 at 6:28 am
Thanks for the great comments!
Question r.e. institution experiences:
To an outsider, your work appears moderately interdisciplinary. You teach classes that explicitly address physics, math, and philosophy, while keeping abreast of both theory and empirical work in your own field. From your Ph.D. to present, do you have any observations about the aspects of an institution that aid interdisciplinary collaboration?
For example, in your experience has collaboration been hindered by “big personalities” at prestigious institutions, or the political dysfunction at state institutions? Socioeconomics or preparation level of student body? Proximity to other major research institutions? Transportation? Campus liqour laws? What makes a *good* interdisciplinary institute, and are there any warning signs to watch for?
Comment #141 September 8th, 2016 at 7:25 am
Arko
You wrote: “If we accept that passing the Turing Test is a good criterion to tell if a test subject has something of a consciousness of the kind humans possess.”
I don’t think the TT is about consciousness, rather it about trying to arrive at an operational even somewhat minimal definition of “thinking”. It tries to answer the question of at what point would we consider a device/program to be “thinking”?
Wikipedia even quotes Turing on this from the original paper.
“I do not wish to give the impression that I think there is no mystery about consciousness. There is, for instance, something of a paradox connected with any attempt to localise it. But I do not think these mysteries necessarily need to be solved before we can answer the question with which we are concerned in this paper.”
Searle goes a step more and tries to show that something could pass the TT and have no consciousness of what it is doing.
The problem is that consciousness is internal and not directly measurable at least at this time. We can surmise other humans and other animals are conscious from their behaviors but we have no way to prove it.
I am interested in what a strong TT would be like. To me it would need to be able to identify TT responses from devices/programs consistently without false positives. It should not falsely identify humans as devices/programs.. This would include distinguishing humans pretending to be computers and computers pretending to be human pretending to be computers. A daunting task when you also toss in the wide range of human possible responses, including unintelligent responses, joking and/or uncooperative responses, as well as normal responses of autistic savants who might be able to do lightning calculations or impressive feats of memorization.
Comment #142 September 8th, 2016 at 9:56 am
Bakkot #138: Your linking add-on sounds like a great idea! And I’d be more than happy to make (easy) changes on my end if it would help.
With threaded comments (like on SlateStarCodex), my main issue is that it’s hard for me to tell what’s new after reading the comments and then coming back to them later. Maintaining a linear sequence but adding automatic links to it sounds like a great solution.
Comment #143 September 8th, 2016 at 10:24 am
helmingstay #139,
Thanks that looks very helpful.
Comment #144 September 8th, 2016 at 11:02 am
Arko #136: By a “strong” TT, I simply meant that the interrogator is neither stupid nor untrained in how to conduct these contests nor hobbled by contest rules in what they’re allowed to ask. As I illustrated with my Eugene Goostman chat, it’s possible to unmask any unsophisticated AI almost immediately, once you realize that your goal is not to have a “natural conversation,” but just to unmask an unsophisticated AI by probing its common sense understanding.
Regarding circularity, I agree but am not particularly concerned about it. When you’re just getting started with an intellectual enterprise, some degree of circularity is unavoidable, because you’re just trying to come up with definitions that match your intuitions, not yet testing them against the external world. E.g. you might start geometry by saying that a line is a thing defined by two points that it passes through, while a point is a thing defined by two intersecting lines. Then later you could ask about the truth or falsehood of the Parallel Postulate or things like that.
In the same way, the Turing Test is defined in terms of humans, and we might choose to call humans intelligent because they can pass something like the TT. So far, so self-referential. OK, but now when we ask what it takes for a machine to pass the TT, things get more interesting…
Comment #145 September 8th, 2016 at 11:05 am
vzn #38, gentzen #57: Since Lagarias came up, let me link to one of his articles on Collatz 3n+1 conjecture, and to his article on the Riemann hypothesis containing his nice elementary problem. However, let me replace the Collatz conjecture with Goldbach’s conjecture for the task “to check whether … proposal allows to make sense of those differences” regarding my thoughts on “logical probability”.
I have found that Scott’s proposal is easier to use for the moment, and allows to nicely understand certain features. If we look at Goldbach’s conjecture, we already know that the probability that it fails for any number we would try to check is extremely small, and gets ever smaller for bigger numbers (i.e. the expected number of different decomposition into the sum of two primes just keeps on growing). So our Bayesian probability that it is correct is basically already extremely close to 1, and we could make as close to 1 as we wish (if we are willing to spend the corresponding computational resources). However, this extremely high Bayesian probability for it being true only means that we have nearly no chance of disproving it, it doesn’t mean that it is provable, and it doesn’t even mean that it is true.
The cool thing of Scotts proposal in this context is the “epsilon”, which allows our best hypothesis “h” to sometimes be wrong, even if it is our best hypothesis based on an extremely huge number of sample points. I like this because it means that even a Bayesian probability arbitrarily close to 1 is no guarantee for truth, which might be a good argument that multiple different Bayesian probabilities arbitrarily close to 1 are “nice to have” in order to feel more confident.
For Riemann it is different. The probabilities are not yet arbitrarily close to one, and it is not immediately obvious that we could push them arbitrarily close to one by evaluating more zeros of the zeta function, or checking Lagarias elementary problem for more numbers. To the contrary, it is even so that the things we can check have many near failures, and there are even two types of failure modes, like that Lagarias inequality could be violated by becoming an equality, and that it could be violated more severely. Here we rather get the impression that there must be a hidden reason why it is never violated, so even so our certainty whether the Riemann hypothesis is true is weaker than for Goldbach’s conjecture, we get the expectation that the underlying reason why it is true is that it is provable.
And I believe this is the central difference here. In the case of the Riemann hypothesis we are somehow finding/collecting evidence that it is provable, while for Goldbach (and probably also for Collatz), we are just collecting evidence that it is true (but not necessarily provably so).
Comment #146 September 8th, 2016 at 11:37 am
If we had a Presidential Test (PT) would what is Aleppo be on it?
What else would?
Comment #147 September 8th, 2016 at 11:55 am
Scott #144:
When you put it like that it just shows how deficient the Turing Test is for what it purports to attempt: provide a machine intelligence/consciousness test.
The Turing Test is grappling with the fact that we easily and intuitively believe in the intelligence/consciousness of other humans, but have a much harder time imagining this same intelligence in a machine. Similarly, we fairly easily intuit the intelligence/consciousness in a animals to a greater or lesser degree ie, anthropomorphizing them. TT is just a way we imagine to try to justify anthropomorphizing AI.
Maybe the fact that it seems so unsatisfying is indication that we should go back and look at our intuition that provides the motivation in the first place: that fellow humans possess something like our own inner experience… ah, but there goes solipsism. And it is this yawning abyss of solipsism that keeps us coming back to the Turing Test and reconciling ourselves to it and let our intuition be damned.
Comment #148 September 8th, 2016 at 2:53 pm
Re #129-131, #133-134 (and related comments by others),
I would highly recommend John Baez’s wonderful 7-part series on Physics Forums Insights, Struggles with the Continuum, starting with Part 1.
Comment #149 September 8th, 2016 at 3:34 pm
@Scott #83: Actually, you can use Amit Sahai’s ideas from the older blog post you mentioned to give a super-easy proof of both Godel’s 1st Theorem (in Rosser’s strong form) and Godel’s 2nd Theorem (Kritchman-Raz not even needed).
See the Lecture 16 slides here:
http://www.cs.cmu.edu/~aada/courses/15251s16/www/schedule.html
This is how I teach it to the CMU freshmen 🙂
(I should add an acknowledgment to Kleene, Amit, and you in those slides…)
Comment #150 September 8th, 2016 at 3:51 pm
#147
I really don’t think Turing intended the test to be a test of consciousness (and maybe not intelligence either since humans often behave in unintelligent ways). See my previous post on that. I am guessing he thought that getting into discussion of consciousness would derail the attempt to provide a useful, operational standard for judging the capabilities of a machine to imitate a human.
Regarding other humans and machines. The TT is extremely limited in that the interaction is solely by words. When we view other humans and animals, we have many other clues as to whether we might reasonably believe that they are conscious. We can usually see them moving. We see they have eyes and ears like we do. We can usually detect what looks like purposeful behavior. My cat who hears my car in the garage when I come home from work and goes to the table where he is usually fed. When we have machine like Ava in Ex Machina, I doubt we will have a problem ascribing consciousness to it.
Comment #151 September 8th, 2016 at 4:03 pm
There’s actually an 8th part to Struggles with the Continuum, but for some reason it doesn’t appear in the “click for complete series” box! It can be found here: https://www.physicsforums.com/insights/struggles-continuum-conclusion/
Comment #152 September 8th, 2016 at 4:10 pm
Scott #142: I’ll see what I can do; it might be a week or two, since classes are about to start up again. In the mean time, including this script in WordPress’s footer will turn most common forms of addressing other comments into links. Not perfect, since it has to guess, but still pretty good. (Try it out by opening the developer console (f12) and pasting in its contents, then look at e.g. my comment.)
You can either put its contents in a script tag or include it with “script src=”; in the latter case I’ll be able to modify it without further intervention from you. This gives me a lot of power, mind, but it’s been the setup at SSC for over a year without me abusing it.
You can email me at (my handle) at gmail, if that’s helpful.
Comment #153 September 8th, 2016 at 5:48 pm
Ryan #149: Thanks so much for that!
And everyone else: THIS (Ryan’s Lecture 16 slides) is a candidate for the greatest exposition of Gödel’s Theorem that’s ever been written. So take a look if that’s something that would interest you.
Comment #154 September 8th, 2016 at 8:06 pm
Sniffnoy #137: With respect to the natural numbers, the straight-line program encoding may indeed be inappropriate:
This is definitely true for the second-order logic definition of the natural numbers. It remains largely true for the first-order logic definition too, because the induction scheme is an important part of the characterization. Note however that for the first-order logic definition, addition and multiplication are crucial too. (I mean this in the sense that you can define any computable function from the natural numbers to the natural numbers, once you have addition and multiplication.)
But that doesn’t mean that the straight-line program encoding is deliberately perverse. Even for the natural numbers, one could argue that disjoint union, cartesian product and the set of functions from A to B correspond well to the operations efficiently provided by that encoding. And the natural numbers are in close relation to finite sets by being their cardinality. Maybe this argument was part of my initial motivations, but those attempts at category theory motivated reasoning have been incredibly time consuming for me, with only few tangible results.
The context were I think that the straight-line program encoding is natural is for storing the elements of a free algebra. For the free group, the slp distinction problem turns out to be actually equivalent to the complement of the identity testing problem for integers (encoded as straight line programs with 1,+,-, and * as operations).
Well, I was curious how someone who studied a closely related problem would judge straight-line programs as an encoding. Of course, I am also curious whether I can modify your judgement slightly more in favor of straight-line program encodings (both for integers and for their real use case as a natural encoding of elements from free algebras).
.
.
Beyond will be dragons, formatting doesn’t work…
.
.
Probably nobody noticed, but up to now I really tried to be as clear and upfront as possible in my comments. This won’t be possible in what follows below, and probably wouldn’t help either. The problem is that what I write below is mostly trivial, because explaining “the real issue” with natural numbers is too hard for me. I will not explain NJ Wildberger’s style of ultra-finitism here, because you will not subscribe to his views anyway. So I will ignore straight-line program encodings now (except as a simple example of an encoding which gets rejected as deliberately perverse). So here are two statements about integers which occurred in this open thread:
In logic, integers (natural numbers) are a tricky subject. They are much more complicated and subtle than bits. And I am not talking about constant factors here. Let us start with the initially removed discussion of the encoding of integer input:
You could use unary encoding, i.e. a long sequence of 1 representing the number, followed by a single 0. But then the answer of a halting oracle that a given computation C would finish in fewer than k-steps would provide little additional information over the mere fact that the computation halts, because reading the number k in unary encoding would take nearly the same amount of time as just running the given computation C until it finishes.
Assuming that the input alphabet is {0,1}, we probably want to use binary encoding for integers. That encoding works best if we know the number of bits required to represent the given integer, or at least an upper bound on the number of bits. We could use the following scheme: If the number is smaller than 255, then we store it directly using 1 byte (8 bits). Otherwise we first store 255 (i.e. 8 ones), followed by the required number of bytes (stored as an integer in the same encoding), followed by the actual bytes representing the integer.
With this simple binary encoding, there are now sequences of input symbols which can no longer be interpreted as a valid encoding of an integer. And if we don’t forbid encodings with unnecessary leading zero bytes, then each integer also has more than one possible encoding. So let’s forbid those encodings too. But there is one invalid encoding which a Turing machine is unable to reject in a finite amount of time: an infinite sequence of bytes with the value 255! You might object that infinite inputs are not allowed. You are right, but if infinite inputs are not allowed, then the Turing machine should try to reject them, no?
You probably agree that there is no block code which can encode all integers. So we could use a prefix code to encode integers. But then a deterministic machine is no longer able to read the numbers backwards. We could use a separator, which actually works, but somehow doesn’t fit into the framework of (pure) codes (for whatever reason). We could use a nondeterministic machine, then we are fine even with arbitrary recognizable variable length codes, and can read them both forward and backward. Not sure whether bifix codes really help.
Note that “constant factors and things like that” have nothing to do with this. What this is really about are synchronization points in the input symbol sequence. Which is important if your machine communicates with other machines (or with an oracle), but less important if your machine just computes alone (starting from an empty initial tape, or a tape with only a finite number of symbols on it).
Comment #155 September 9th, 2016 at 12:22 am
Folks, stop worrying about different parts of Baez’s Struggles With the Continuum. He has uploaded it on arXiv: http://arxiv.org/pdf/1609.01421v1.pdf
Scott, let me get back to you.
Comment #156 September 9th, 2016 at 12:57 am
Scott #144: I am not very convinced, because then my construction of a strong TT itself seems contrived. I need to have an a priori idea about what kind of thinking my AI candidate claims to be able to display. My point is, given such an a priori idea about any candidate AI, it seems always possible to construct a TT that such a candidate would fail. What do you think?
I think the best any form of a TT can be hoped to achieve is offer the interrogator a strict understanding of just how much a candidate intelligence can “think” within the constraints of that TT. As James Cross points out, it really isn’t a good candidate test for evaluating intelligence per se.
Also, the example you offer about circularity is a bit inexact: reference to points for defining a line is a necessary condition, whereas reference to lines for defining points seems merely a sufficient condition.
I agree that some bit of circularity is inevitable in any germinating intellectual enterprise (heck, how else is progress supposed to take place towards attaining any form of objectivity!), but I think we both agree that when found, a circularity should at least be attempted to be removed, or be made known at the very least.
Comment #157 September 9th, 2016 at 8:22 am
I’ve never bought the argument that Godel’s first incompleteness theorem is made super easy just by knowing from Turing that the halting problem is undecidable. Sure, it follows once you know that the axioms in your sufficiently expressive formal system and all provable theorems are recursively enumerable, which by the Church-Turing thesis you would always expect. But this is a hand waving proof because the Church-Turing thesis isn’t rigorous mathematics! To rigorously prove Godel’s theorem for a specific axiom system like ZFC you would actually have to construct the Turing machine that enumerates all proofs in your system. I suspect this Turing machine-based proof is just as formal and messy as what Godel had to do in recursively defining 46 functions.
Comment #158 September 9th, 2016 at 12:23 pm
William #157: Standards of rigor can change over time, as people get accustomed to something. Before computers existed, it took 30 pages of laborious argument to convince people that “S has a proof in ZFC” can itself be encoded as an arithmetical statement. Nowadays, look at any refereed journal paper in theoretical computer science, and you’ll find numerous statements like, “clearly one can write a program that enumerates over all x, and for each one, checks the following…” This is considered perfectly rigorous, because it IS perfectly rigorous, just as much as comparable statements you could find in the literature of other parts of math. The world has changed; what once required argument is now obvious.
But there’s even a deeper point. If you look at Ryan O’Donnell’s slides, he proves, with essentially ZERO handwaving, that any consistent, computable system of axioms able to talk about Turing machines can’t prove its own consistency. And I actually see that as the much more fundamental statement than that PA or ZFC or some other specific system can’t do it. For not only is it more general, but if PA or ZFC didn’t let their theorems be computably listed, then so much the worse for them! It would mean they were useless as formal systems, rather than merely incomplete.
Comment #159 September 9th, 2016 at 12:32 pm
Thanks Arko, Sniffnoy, and Chris W. for sharing that “Struggles with the Continuum” paper by John C. Baez. I will attempt to read and understand it over the weekend.
If you’re interested in digital physics models, independent film, and retro computing technology, please check out the trailer for my film “Digital Physics”.
https://vimeo.com/ondemand/digitalphysics/
Comment #160 September 9th, 2016 at 3:13 pm
Bakkot #138, Scott #142: it’s been written already…
Comment #161 September 9th, 2016 at 10:01 pm
John Baez’ “Struggles with the continuum” (arXiv:1609.01421) and the Martinis/Google group’s “Characterizing quantum supremacy in near-term devices” (arXiv:1608.00263) each provide enjoyable illumination to the other, as follows.
Drawing upon the reasoning of Baez’ Section 3 “Classical electrodynamics of point particles” and Section 4 “Quantum field theory”, we adopt what chemists call “Hartree units”. These are the (unique) units of mass, length, time, and charge such that Planck’s constant, the electron mass, the Bohr radius, and the Hartree energy all have numerical value unity.
It is an easy exercise to establish that in Hartree units, everything becomes a function of the fine structure constant \(\alpha\). In particular:
\(\displaystyle\begin{array}{rc@{\,=\,}l}
\text{von Klitzing constant}&R_{\text{K}}&2\pi\\
\text{Josephson constant}&K_{\text{J}}&1/\pi\\
\text{light speed}&c&\alpha^{-1}\\
\text{London penetration depth}&\lambda_{\text{L}}&\tfrac{1}{2\sqrt{\pi}}\,\alpha^{-1}\\
\text{magnetic constant}&\mu_{0}&4\pi\alpha^2\\
\text{photon-photon scattering}&\sigma_{\gamma\gamma}&\tfrac{973}{10125\pi}\,\alpha^{18}
\end{array}\)
Here the cross-section \(\sigma_{\gamma\gamma}\) is evaluated for Hartree-energy photons.
The \(\alpha^{18}\)-dependence of \(\sigma_{\gamma\gamma}\) is pretty remarkable, isn’t it? Here we see that parameters that seem “unnaturally small” in fact arise very naturally in gauge field theories.
In contrast, electrostatic dynamical properties — such as chemical binding energies, phonon spectra, specific heats, and superconducting transition temperatures — all are unaffected by (what amounts to) speeding up light or slowing down light.
It is natural to ask “What value of \(\alpha\) makes quantum supremacy most easy to demonstrate” with Martinis/Google superconducting qubit arrays. The enjoyable lesson (for me) is that nature’s value of \(\alpha\) is pretty nearly optimal, or equivalently, the speed of light can’t be varied much from its present value, and still hope to demonstrate quantum supremacy wih superconducting qubit arrays.
For if we slow light to 1% of its present speed, then photon-photon scattering cross-sections become so enormous, that light behaves more like an ideal gas than a linear field.
Conversely, if we accelerate light to 100X its present speed, then magnetic fields penetrate so deeply into superconducting junctions, that pair-tunneling is quenched, such our qubit arrays cease to exhibit quantum flux-dependence…
These brief “Fermi-type” calculations barely scratch the surface of what seems (at first sight), to be a conspiracy by nature, in which the speed of light is adjusted so as to maximally encourage us humans to conceive that demonstratoons of quantum supremacy may be just barely technologically feasible. 🙂
Comment #162 September 10th, 2016 at 11:09 am
In further news, the Harvard/Princeton course/seminar “Proofs, beliefs and algorithms through the lens of Sum of Squares”, conducted by Boaz Barak (with Pablo Parrilo) at Harvard, and by David Steurer and Pravesh Kothari at Princeton, has posted its first lecture notes. For background, see Barak & Steurer’s arXiv:1404.5236 and the course announcement on the weblog Windows On Theory.
Much can be said in appreciation of the specific topic of these lectures (namely Sum-of-Squares algorithms) … but it’s mighty tough to better the discussion given in the lecture notes themselves.
So instead let’s consider the primary framing of the BPSK lectures via the idiom “through the lens”. After all, an arXiv full-text search finds about two hundred “through the lens” articles — some literal, but most metaphorical — and so the BPSK team is not alone in its embrace of metaphorical lens-framing!
Compound optical devices for human use (such as telescopes and microscopes) combine an objective lens with an ocular lens, with the objective lens serving to gather as much light as possible into an optical image, and the ocular lens serving to provide a magnified view of that image. Binocular further improve the image by providing it to both eyes, and hence, both hemispheres of the brain.
In this extended lens-framing metaphor, the “objective lens” of the BPSK lectures is algebraic geometry, the “ocular lens” of the the BPSK lectures is the Sum-of-Squares algorithm, and the “binocular view” is set forth explicitly in the Introduction of arXiv:1404.5236
Not the least excellent aspect of the BPSK lectures (as I read them) is the generality of their overall method. For we are to consider, first, that the “objective lens” of algebraic geometry has vast light-gathering power.
Second, we are free to choose from a vast inventory of “ocular lenses”; as just two examples among many we may choose to closely inspect any of the technological paths proposed for demonstrating of Quantum Supremacy and/or any of the John Baez’ “Struggles with the continuum” (of arXiv:1609.01421).
Third, our motivations for undertaking these investigations can range freely over the left-hemisphere to right-hemisphere “binocular” set of reasons that Terry Tao enumerates in his essay “What is Good Mathematics” (arXiv:math/0702396).
Hence, this grateful appreciation is extended to Boaz Barak, Pablo Parrilo, David Steurer, and Pravesh Kothari, for conceiving and sharing a set of lectures that illuminate complexity theory through a set of mathematical lenses that has extraordinary light-gathering capacity and image-focusing power.
Comment #163 September 10th, 2016 at 11:21 am
Anyone interested in a fast, easy to use code for molecular dynamics of large systems (proteins, etc) should look at the excellent Yasara (www.yasara.com). I’ve been using it for years and the developer Elmar Krieger is unfailingly helpful.
Comment #164 September 10th, 2016 at 1:46 pm
Arko #156
Actually instead of the TT, it might be better to have an AI candidate participate as an equal with humans in a game that required an understanding of human motivation and deception.
Something like StarPower.
https://en.wikipedia.org/wiki/StarPower_(game)
The success of the AI would be judged by how closely the behaviors of the AI mimicked those of a typical human.
Comment #165 September 10th, 2016 at 9:54 pm
Sniffnoy wrote:
Fixed! Thanks, and thanks to Chris Weed for letting me know about this mistake. You can get all of “Struggles with the Continuum” as a single PDF file on my website or on the arXiv — but right now, the website version is more up-to-date.
Comment #166 September 10th, 2016 at 10:02 pm
Douglas Knight wrote:
Yes, that’s widely believed. It’s widely believed that QED does not. But nobody has proved that any interacting quantum field theory exists in 4 dimensions – i.e., exists as a mathematical structure obeying any of the various usual axioms for quantum field theory. Sad but true!
Comment #167 September 11th, 2016 at 12:07 am
John K. Clark wrote:
Because it’s over 500 pages long and he’s really, really, really bad at explaining things.
People want to understand it, but when you read dozens and dozens of pages of complicated definitions and you have no clue why someone is making those definitions, you tend to give up and do something else.
For a professional mathematician, reading a long proof is not a matter of going through it in a linear fashion and seeing whether each sentence follows logically from the preceding one. Instead one starts by tries to understand the key steps in the proof: the main definitions, the main lemmas, etcetera. One tries to see why a proof of this general sort might make sense. Then one starts digging into the details.
This strategy is generally very good. It hits roadblocks when there are a large number of definitions that are complicated and unfamiliar, without nice examples. That’s a demoralizing experience. And Mochizuki’s proof presents these roadblocks in a truly massive way.
Read, for example, the top answer to the Quora question What is a Hodge theater as mentioned in the first paper by Shinichi Mochizuki? This concept is, apparently, fundamental to his proof. But the answer begins “I’m afraid this is not an answerable question….”
You can watch a video giving the definition of Hodge theater, but the speaker starts by saying “I’m going to give the definition, but you’ll see that it’s not so enlightening”. In addition, he assumes you already know about Frobenioids – another concept Mochizuki invented.
A Scientific American article writes:
So this is really quite a remarkable situation, and I’m very curious to know what will happen. But not curious enough to fight my way through the proof. I tried, once.
Comment #168 September 11th, 2016 at 12:34 am
Daniel Reeves #126: Sorry for the delay! No, your proposed modification to our CTC algorithm doesn’t work, because 0 or 666 or whatever non-solutions were mapped to could simply be returned as the fixed point—thereby avoiding the need to solve a hard problem. I’m pretty sure the CTC algorithms that we give in our paper are close to the simplest ones possible (a statement I only venture because the algorithms ARE so simple that there aren’t many simpler possibilities, and I don’t think any of them work).
The Shakespeare story is just meant for inspiration—it captures the idea of a fixed point, but not the further idea of a probabilistic fixed point, or (crucially) that there need to be no OTHER fixed points besides the desired one.
Comment #169 September 11th, 2016 at 11:39 am
This new paper from Harvard & MIT researchers uses information theory to show that Hamiltonians link deep learning neural networks to the laws of physics:
http://arxiv.org/pdf/1608.08225v1.pdf
Do you agree with what they write about the complexity?
Comment #170 September 11th, 2016 at 4:06 pm
Scott #168: Thanks! You’re right. And that’s funny because that’s exactly what happens in Harry Potter and the Methods of Rationality when Harry fails to fully specify the domain of his function.
I could patch my proposal like so:
M(x) = {
0 if x = 1
1 if x = 0
x if x is a solution
0 otherwise
}
But, like you say, not really simpler than the loop you constructed.
Next question: What happens if M simply doesn’t have a fixed point? What does the universe do then??
Comment #171 September 11th, 2016 at 4:28 pm
Daniel #170: Your new program has no deterministic fixed points other than the solution x. But it does have a probabilistic fixed point: namely, 0 with probability 1/2 and 1 with probability 1/2. In the programs in my and Watrous’s paper, there aren’t even probabilistic fixed points other than the one that encodes the solution.
This is also the answer to your second question: in Deutsch’s proposal, you need to allow probabilistic (or, in his version, even quantum) fixed points—precisely because once you do, you can prove a theorem saying that at least one fixed point always exists, as long as there’s a finite upper bound on your program’s input and output size. The Grandfather Paradox is simply the statement that, even with 1-bit input and output, fixed points need not exist if you restrict yourself to deterministic ones only.
Comment #172 September 11th, 2016 at 6:00 pm
John Sidles #127:
Oh, I guess that was directed towards me. Or at least it is a good opportunity to explain a bit more. For complexity theory, oracles are fine. I have already accepted the existence of Turing machines (because I want to be able to talk about consistency), and the typical oracle machines occurring in complexity theory are weaker than Turing machines.
My original question (from Jul 6 ’14) asked whether the existence of Turing machines is a stronger ontological commitment than the existence of natural numbers. Especially, I wanted to know whether it allowed to prove the model existence theorem.
Only after reading Max Tegmark did I realize that the existence of Turing machines allowed to prove the existence of certain equivalence relations and the existence of certain subsets of the natural numbers. So it turned out that the question had meaningful answers, but neither my own answer nor the other answers came even close to such a meaningful answer.
At least I became convinced that there are reasonable answer to such questions. I guess it is this conviction which creates confusion and controversy, more than the actual answers.
.
.
In logic, one can get defeated by the natural numbers time and again. Already Gödel was surprised that Turing machines apparently manage to not get defeated by the natural numbers. And this is good, otherwise we wouldn’t even be able to talk about consistency and do logic as we now know it. But the natural numbers can’t be defeated so easily, this would contradict the “law of conservation of difficulty”. The question is, where are they hiding, and when will they strike again? My guess is that they will strike again as soon as we use oracles.
But only some types of oracles are dangerous. If I have an oracle that solves 3SAT (and hence is equivalent to any oracle for NP), then this is a white box oracle, in the sense nothing can hide inside of it. We know exactly what it must be doing. This white box character is typically implicitly implied when we talk of oracles. A black-box version of oracles is used for some separations of complexity classes (especially in the context of quantum computing). However, they are normally called “black-box model” instead of oracle, precisely because talk about oracles has this implicit white box character. Questioning the existence of an oracle for HALT basically just questions whether that oracle really has the white box property.
Say you buy a brand new TM with oracle for HALT from the company D-Wine. How can you be sure that they didn’t cheat you? They assure you that it passed both their PA and ZFC test suites. After you receive the machine, you run your Woodin test suite on it, and it fails. Can you conclude that the machine is rubbish?
Comment #173 September 11th, 2016 at 9:44 pm
John Baez #167: May be, as Plank said, we would understand Mochizuki’s proof a few funerals later!
Also, perhaps, he himself doesn’t quite fully “understand” the proof. As in intuitively, as against just mechanically following through the steps. Which may be why he finds it so hard to explain it to anyone.
Comment #174 September 11th, 2016 at 10:59 pm
James #164: While that certainly sounds like an improvement, it doesn’t address the fundamental problem that I have been trying to put forward, but had been having trouble articulating so far. Namely, if we are to gain any understanding into the fundamental nature of consciousness and intelligent behavior, can we settle for a theory that is comfortable with circular arguments?
E.g., if we were to arrange for a direct face-off between an AI candidate and a “typical” human, then what kind of human could be called typical in the first place? A sufficiently strong test could always be designed that will be failed by a majority human population. If we then pick one individual from this population and have them face-off against a candidate AI, I doubt if anything fruitful could be inferred from such an exercise.
On the other hand, if we designed a test that would be passed by the majority of a population, then we would end up accusing ourselves of moral dishonesty.
Perhaps we should not even look for passing/failing a test, but how a candidate AI “handles” the information given to it, as in how a candidate AI “argues” with incomplete data.
On the other hand, as Sean Carroll discusses Downward Causation on his blog, IF we accept that no matter how difficult it might be to understand consciousness and intelligent behavior, it MUST be consistent with the physical laws, then we must make an attempt to gradually move towards a language that talks about consciousness in an objective way.
But of course, I think the above paragraph is written uselessly since we all agree that that indeed is the goal.
Comment #175 September 12th, 2016 at 6:41 am
That question (as I phrased it) was consciously grounded in the ideas of Juris Hartmanis’ foresighted and much-cited monograph Feasible computations and provable complexity properties (1978). As Hartmanis put it:
Today, 38 years post-Hartmanis, the Barak  / Parrilo / Steurer / Kothari course “Proofs, beliefs and algorithms through the lens of Sum of Squares” can be appreciated (per comment #162) as focusing research attention upon the vast vigorous vistas of modern complexity theory in which Hartmanis-class questions are studied through algebraic lenses.
Comment #176 September 12th, 2016 at 1:15 pm
Juxtaposing Scott’s Busy Beaver and Aumann articles: Is it a just a coincidence that all examples of noncomputable functions pertain to figuring out what other programs will do, which in some sense is the notion of higher order beliefs (which I think is central to all of economics and other social disciplines)?
Comment #177 September 12th, 2016 at 3:04 pm
As long as we have an open forum here, I’d like to comment on the perception by some people that famous mathematicians don’t work on hard math problems.
I was looking at a YouTube video of a Terence Tao lecture the other day, and during the Q&A which followed, someone asked him if he worked on famous problems like the Riemann Hypothesis or P vs NP. He replied that he thought RH would be the second to the last famous problem solved, and P vs NP would be the last. He doesn’t work on such problems, because it is possible to work on them forever, and not solve them. He prefers to work on things where some path to a solution in a reasonable amount of time is apparent.
Another famous mathematician, whose name escapes me at the moment, was asked why he didn’t work on the Riemann Hypothesis. He replied that it would take him four years to read into all the work done on the problem, and after that, the likely outcome would be that he would work on it for the rest of his life and not solve it.
I was wondering if the seeming reluctance of the top mathematicians to work on intractable things is impeding our progress in understanding them. Would the world be better off if a few good mathematicians were willing to waste their entire lives trying to solve these problems, even if it meant they would likely leave no legacy.
Comment #178 September 12th, 2016 at 7:51 pm
venky #176:
Is it a just a coincidence that all examples of noncomputable functions pertain to figuring out what other programs will do, which in some sense is the notion of higher order beliefs (which I think is central to all of economics and other social disciplines)?
The trouble is that you can make up questions that seem to have nothing to do with computability or self-referentiality on the surface—for example, among all sets of n tiles that don’t tile the entire plane, what’s the one that tiles the largest part of the plane?—but that turn out to secretly contain the halting problem and the Busy Beaver function anyway. On the other hand, yes, it’s true that all known proofs of the noncomputability of explicit problems, ultimately make some appeal somewhere to self-reference, which is a very interesting fact.
Comment #179 September 12th, 2016 at 8:03 pm
Enochian #177: I can make two points. Firstly, math is a cumulative enterprise. Even Andrew Wiles saw as far as he did only by standing on the lemma-encrusted shoulders of giants. Thus, rather than working their whole life on the Riemann Hypothesis and publishing nothing, it would likely be more valuable for great mathematicians to publish partial results and insights related to RH that future mathematicians could then build on.
Secondly, there are other alternatives besides directly attacking the great open problems, and working on tiny problems that lead to nothing outside of themselves. You can also work on easier, solvable problems that are inspired in some way by trying to illuminate the big problems. A significant part of the algebraic number theory of the 19th and 20th centuries bore that sort of relationship to Fermat’s Last Theorem, and a significant part of complexity theory bears that relationship to P vs. NP. And Terry Tao has certainly done that sort of illumination work with, for example, the Navier-Stokes smoothness conjecture and the twin primes conjecture.
Comment #180 September 13th, 2016 at 12:52 am
John Baez #165: Thank you for fixing that!
Meanwhile, speak of the devil, MIRI has a new paper about logical probability. I haven’t looked at this at all yet so uh that’s about all I can say about it at the moment. (Not like I’m really qualified to evaluate papers on this subject anyway, I wouldn’t be saying anything not in the summary I expect.)
Comment #181 September 13th, 2016 at 1:15 am
OK now having actually read the summary… it seems like they may have actually come up with the first sensible notion of “logical probability”! If so… wow!
Comment #182 September 13th, 2016 at 9:28 am
…ok, having now actually read the *intro* (which is about as far as I’m likely to go 😛 ) what stands out to me is the *failure* of “criterion 13” — the criterion that, as the program sees more examples of a phenomenon (specifically, of a Π_1 statement), its probability for that statement goes to 1. Apparently this is *incompatible* with the criteria they do achieve! This seems like a deficiency to me, but if it’s actually incompatible, perhaps it shouldn’t be regarded as one? Hm. Not sure what to make of this.
Comment #183 September 13th, 2016 at 10:38 pm
Not all NP reductions are equal. When you reduce one NP problem to another NP problem, the input size (N) changes for most.
For example, converting SAT to clique changes the input size to order(power) of 2 where as clique to independent set or vice versa retains the input size (N).
Also, even if P equals NP, the world is not going to end. Problems are not going to disappear. Creativity is not going be replaced.
It will only increase the knowledge about context, environment of the problem and its solution.
We missed so many things on not understanding subtle differences. Also not trying out.
Lets us say that there exists an o(n^4) constructive, usable with negligible constant c algorithm for one of the problem, do you think that it is going to help solve all the problems?
Unless we can find o(n^2) or o(n^3) constructive usable algorithm for one of the problem, we don’t need to worry about the apocalypse.
Note: most of the NP problems are graph related. So, here, I mean n to |V| and not |E|.
Comment #184 September 14th, 2016 at 4:38 pm
Scott, do you think Snowden should be granted a presidential pardon? Will you blog about it?
Comment #185 September 14th, 2016 at 4:39 pm
Sniffnoy #182: You can look at the earlier (Sawin and Demski, 2013) for a short, hopefully self-contained, justification that you don’t want that property.
Comment #186 September 14th, 2016 at 7:22 pm
Jay #184: If I were Obama, I’d regard that as a very non-obvious question, and would try to weigh what other realistic options Snowden had available, whether he had endangered American field operatives, how hard he’d tried not to endanger them, etc. (some of the relevant information might still be classified). In any case, given that Snowden seems to have acted out of genuine patriotic conviction and to have spurred necessary reforms, and that something like a third of Americans support his return, I do hope he eventually gets pardoned, if not by Obama then by a future president.
Comment #187 September 14th, 2016 at 11:00 pm
Sam #185: Oh, thanks! I asked about this over on SSC and someone pointed me to that as well. That does seem to suggest that the answer really is “No, we don’t want #13”.
However part of the proof doesn’t make sense to me. Are we talking about Π_2 sentences, or Π_2 statements with free variables allowed? If the former, the end of the proof doesn’t make sense to me (whether a set is Π/Σ/Δ_whatever is about predicates in one variable, not sentences with no free variables); and if it’s not about Π_2 sentences but Π_2 statements more generally with free variables allowed, then the preceding parts don’t make sense (e.g. how are you going to talk about their truth or falsehood, and why are we assigning them probabilities?).
Can anyone perhaps clear this up?
Comment #188 September 14th, 2016 at 11:22 pm
Oh, hm — (I’m basically copying this from a comment over on SSC) — maybe Δ_2 is meant as a class of (equivalence classes of) statements, those Σ_2 statements that are provably equivalent to Π_2 statements.
If you’re thinking about truth, like I’m used to (I am not a logician 😛 ), considering equivalence classes of sentences is stupid, because there’s only two, true and false; you need free variables for it to be interesting.
But if you’re thinking about provable equivalence, then you could talk about “Δ_2” sentences, and say, yup, that’s a strict subset of Π_2 sentences.
If that’s what meant, then indeed, that makes sense (I’ll just assume that the assertion that the inclusion of Δ_2 in Π_2 is proper is indeed true, but that seems pretty believable). If not, then…?
Comment #189 September 15th, 2016 at 12:07 pm
That’s right. 🙂 There are two notions here: Π_n sets, which are defined more extensionally (sets of numbers such that there exists a formula) and Π_n statements, which are defined in terms of provability. This paper deals with the latter, as you have deduced.
Regarding the inclusion, it needs to be strict or the *arithmetical* hierarchy collapses. Unlike the polynomial hierarchy in complexity theory, we have a fairly simple proof that this doesn’t happen; if it collapsed to the nth level, you could write a truth predicate for arbitrary statements by saying “this statement is equivalent to a true Σ_n statement”. We have truth predicates for bounded quantifier depth by explicit construction, but one can’t exist for all statements by Tarski’s undefinability theorem.
Comment #190 September 15th, 2016 at 12:51 pm
Huh! But that’s a different arithmetical hierarchy now than the usual one, isn’t it? I’ve normally heard that referring to the first notion of Π/Σ/Δ_n…
Comment #191 September 15th, 2016 at 1:56 pm
Scott #185,
I feel hard to understand why you regard this as non-obvious.
Of course I read your point that maybe he armed someone and Obama knows it but it’s classified, but… you believe that, seriously?
If this was true, why wouldn’t they say it just as you did?
“For securit reasons we can’t provide any details, but we identified three specific agents that have been hurted because of Snowden’s leak. The details are known by the president. And candidate Trump, so you can ask Putin.”.
To me the actual official declarations make clear that he armed no single one, except in the weak sense that now everyone knows what bad methods USA spies were using, it might be a little harder to use the very same bad methods again.
But anyway, I find fascinating to have the US perspective on this (only one third… due!), so thanks for your sharing your thoughts.
Comment #192 September 15th, 2016 at 2:52 pm
Sniffnoy #190: Yeah, this is the arithmetical hierarchy for sentences rather than sets. My proof is about sentences though, so this should be fine, no?
Comment #193 September 15th, 2016 at 3:13 pm
Yes, yes, it’s just confusing to have it refer to both those things! Anyway thank you for clarifying things!
Comment #194 September 15th, 2016 at 3:25 pm
Also, I just realized we don’t actually need this; Sawin and Demski just use the fact that their statement is Π_2, they don’t care whether it’s also Σ_2.
Comment #195 September 17th, 2016 at 10:12 am
Is there any commenting service like disqus that allows you to use math in comments? I’d like to start a blog and I’d prefer a statc website, but I’d like to support user comments, but I can’t find a good solution for support of math in comments. I wonder if anyone here knows of a good solution.
Comment #196 September 17th, 2016 at 3:31 pm
Some time ago, US attacked Syrian army positions, killing 60 people and wounding 100. This came after several days ago a ceasefire agreement was reached between Russia and US, and after US refused to publish the text of the agreements reached. US accused the Syrian army and Russia to not let humanitarian aid into Aleppo, while knowing that the obstacles were that their “allies” were continuing shooting and did not let inspect the trucks with “humanitarian aid”.
For the information of all those who call to vote for Clinton.
I personally think you are either mad or simply immoral, which is more probable.
I will not bother you any longer with my naive posts.
Comment #197 September 17th, 2016 at 5:36 pm
For the (intended) benefit of Shtetl Optimized readers, please let me recommend the Notices of the AMS on-line archive of “What is…<insert topic>?” essays.
Three great virtues of the AMS “What is …” essays are: (1) they’re written by experts, (2) for nonexperts, and (3) they’re short (two pages).
For example, Timothy Chow’s “What is a natural proof?” (2011) helpfully illuminates the mathematical context of the above Sam / Sniffnoy comments.
Regardless of a person’s STEAM-interests, it’s no bad thing to systematically page through the entire AMS “What is…?” archive. All but the highest-level experts will find a half-dozen or more friendly essays. 🙂
Comment #198 September 17th, 2016 at 8:02 pm
Two questions:
1. Do you have any thoughts or tips on how quantum computing could be used to study earthquakes?
2. What is your secret to being a prolific writer?
Comment #199 September 17th, 2016 at 8:10 pm
Ninmesara 195, (1) Discourse ought to support mathjax but (a) I don’t know that it does and (b) it might be forum rather than a commenting platform. (2) Intensedebate has a mathjax plugin.
Why do you want a static site? If you’re going to load comments in an iframe, why not have two sites, a static one for your content and a dynamic one for the comments, running a stripped down wordpress that’s just comments, but thus can have mathjax?
Comment #200 September 19th, 2016 at 5:13 am
@Duglas Knight #199, I’ll try them both, thank you. I’d prefer a static website because it’s made of simple files, and seems easier to mantain, but if it is the only way to have math in comments I’ll just use something like wordpress. Thank you for your time.
Comment #201 September 19th, 2016 at 5:30 pm
A couple of nerdy observations:
(1) StackExchange’s admins host their blogs through GitHub. Yes, GitHub offers markdown-based latex-compatible blog-hosting comment-accommodating (via Jekyll). The GitHub/Jekyll environment is “expert tolerant” rather than “user friendly”; for some folks this is a desirable feature. 🙂
(2) With a view toward a humorous post I searched the arxiv for recent works containing the string “Kähler”, on the grounds that “The most interesting geometric structure [on manifolds] is the Kähler structure” (from Shing-Tung Yau’s “Perspectives on geometric analysis “, arXiv:math/0602363).
To my surprise the first two weeks of September saw 51 Kähler-containing arxiv articles — too many to joke usefully about — among which two physically-motivated quantum-dynamical data-heavy articles particularly stood out as interesting to Shtetl Optimized readers:
• Zhao, Price, Liu, Jacome and Gemelke “Dynamical Gauge Effects and Holographic Scaling of Non-Equilibrium Motion in a Disordered and Dissipative Atomic Gas” (arxiv 1609.02163).
• Atiyah and Manton, “Complex Geometry of Nuclei and Atoms” (arxiv 1609.02816).
The Zhao et al. article has plenty of ingenious meat-and-potatoes quantum informatic physics, but is sylistically unremarkable.
In contrast the Atiyah/Manton article exhibits (pretty spectacularly) about five of Shtetl Optimize’s “Ten Signs a Claimed Mathematical Breakthrough is Wrong. And yet it’s imprudent to dismiss out-of-hand works by mathematicians of the caliber of Michael Atiyah. To reverse Niels Bohr’s maxim, if the Atiyah/Manton article is wrong, it won’t be for lack of craziness.
What Huck Finn said of Pilgrim’s Progress can be said of both articles: “The statements is interesting, but tough.” Hence (as it seemed to me) no jokes were indicated.
Comment #202 September 22nd, 2016 at 1:02 am
1. Any chance what MIRI is pontificating about will ever converge to what applied AI people are doing, ie ‘deep learning?
2. Any chance SO will ever get a mobile site?