Major unsolved problems in theoretical computer science?
cstheory.stackexchange.com
cstheory.stackexchange.com
It is excellently written, but by no means a light read. If you put in the time and effort, you will come out on the other side with a great foundation, and deep understanding and mastery of the topics.
However, it's definitely not an introductory book, and some background in math will be very helpful.
I'd also check out these threads:
Ask HN: Best Mathematics book for complete noobie? http://news.ycombinator.com/item?id=755043
Ask HN: good math books http://news.ycombinator.com/item?id=665029
Ask HN: Learning advanced math http://news.ycombinator.com/item?id=1753029
Although now that I think of it, those may also have been (re)phrased in terms of computational complexity.
I think they should.
What makes something computation? What is it about a physical process that means it is performing computation? We do not have good answers to this question. (Turing Machines are a model of a computational device, not an account of what computation is).
We often characterise computation as information processing, but precisely what does this mean? What is information? There is such a lack of clarity surrounding this notion which seems so fundamental to CS. People often think that Information Theory provides an answer, but it doesn't really enlighten us about what information is and what its nature is.
I think part of the thing here is that theoretical computer science gets equated with maths, whereas these are not mathematical problems (or at least I do not think they are).
Information theory provides a definition. That definition turns out to be an extremely useful abstraction in a lot of mathematical theorems, and to some extent matches the intuitions we have about information.
If there's a problem with the definition, and it doesn't match up with your idea of what information really is, then it's easy to come up with new definitions; if they're useful, they might even take off.
But it's very hard for a field to answer questions like "what is X, and what is its nature?", because it's not clear what kind of answer would suffice, for any value of X.
I don't think this is a matter of definition.
Here's an analogy. Back before we had an understanding of matter in terms of atomic details (or anything deeper than that), people could have disputed about what is a liquid and what is a solid and what is a gas. Different people might have given different definitions of these in terms of qualities that differentiated them from each other ("solids maintain their shape", "a gas does not weigh much" etc).
But we now know that this question was not a matter of definition but a matter of understanding what was actually going on underneath the phenomenal appearances.
Understanding what a liquid is not a matter of definition, it's a matter of understanding how the phenomena actually works. And in this case we have even been able to show the categories we thought existed weren't even literally different categories.
Returning to the question of what information is, the idea that it's just something to be defined in one of a number of ways is an assumption.
It's programs and programmers all the way down. Or up, if you're Kardashevly inclined. The neat thing about information is that it can probably pass through boundaries of cosmological scale. The neat thing about intelligence is that it emerges, and that it wants to pass through boundaries of cosmological scale. I feel that general / special relativity has something to say about this -- that these laws permit some sort of communication across scales, and that the universe is but a bunch of astronomers and molecular physicists nerding it out. The photons that are helping you read this text is actually composed of subatomic Voyager Golden Phonograph Records with Carl Sagan's signature on each one. Billions and billions of them, into a sea of intergalactic neurons causing a glorious dawn of awakening in your head.
- copyright 2012 Jae Kwon
I've said it plenty of times already in this thread, but I do not think questions of "what is X" are answered by giving a definition.
The are empirical questions, and your job is to try and figure out as best you can how the details work. Reality chooses what the answers are, it's not a matter of you choosing the definition you like.
Anyways, I agree with everything that you've said, I just don't believe we can fully know how the phenomena actually works -- there are infinitely many ways in which it could work, all the time. To observe phenomena empirically in order to figure out how things further work, is to further isolate your existence into a remote section of the possible universes (and sometimes open your known universe up to new opportunities). I prefer to spend my time making reality rather than being chosen by it, which feels more like an active enterprise. In the end it doesn't matter. Have faith in science, or your ability to shape your world, or whatever that engages your computer noggin. :)
-- copyright 2012 Jae Kwon
It transforms input to output -- some computation systems are just less powerful than others :-P
People often think that Information Theory provides an answer, but it doesn't really enlighten us about what information is and what its nature is.
Can you point to any particular problems with the notion of information as that which reduces entropy (which is itself a quantification of what is unknown about some system)?
I do not think that 'that which reduces entropy' is an account of information.
How is a system informed by an input that 'carries information'? What details is the system able to 'learn about' from that input/information? What's happening there is just a physical interaction of the 'inputs' interacting with the system.
How is that information related to the meaning of the information - how does that work?
If the brain is just computation, how does the "semantic information" in the brain work?
It processes the input to determine what actions to take next.
What details is the system able to 'learn about' from that input/information?
Some facility for conditional execution (not just something like an "if...then...else" control structure -- the ability to compute non-constant functions).
What's happening there is just a physical interaction of the 'inputs' interacting with the system.
So?
How is that information related to the meaning of the information - how does that work? If the brain is just computation, how does the "semantic information" in the brain work?
What is "meaning of the information"? What is "semantic information"?
So what qualifies as an input? What qualifies as an action? How do you tell if some physical system, e.g. some biological system, contains 'inputs' and 'actions'?
What's happening there is just a physical interaction of the 'inputs' interacting with the system. So?
See my last point.
How is that information related to the meaning of the information - how does that work? If the brain is just computation, how does the "semantic information" in the brain work? -> What is "meaning of the information"? What is "semantic information"?
Information informs about certain details, a system can take the information and understand its meaning. 'semantic information' - sometimes people use this notion to distinguish between 'data' and 'information' that is more meaningful, like the sort of information that humans can process.
That which affects the system
What qualifies as an action?
Changes in the system's internal state or output
How do you tell if some physical system, e.g. some biological system, contains 'inputs' and 'actions'?
You can test whether its state changes in response to external stimuli (n.b. this is no way to test this perfectly).
See my last point.
Looking back, it seems like you think I've made some claim about the system having "learned" something.
Information informs about certain details, a system can take the information and understand its meaning.
I agree that a system which computes can take the information and act in a way that depends on it, but what do you mean by "understand"?
sometimes people use this notion to distinguish between 'data' and 'information' that is more meaningful, like the sort of information that humans can process.
This is not a definition of either term I asked about.
That applies to any causal interaction with the system. What do you mean by 'system'? How do you objectively determine whether some physical details are a 'system'?
What qualifies as an action? -> Changes in the system's internal state or output
Same kinds of issues. What is the objective criteria for 'system', 'internal state', 'output'? What are the relevant sorts of 'changes' - there's all sorts of physical changes that are not relevant.
How do you tell if some physical system, e.g. some biological system, contains 'inputs' and 'actions'? -> You can test whether its state changes in response to external stimuli (n.b. this is no way to test this perfectly).
but you need some objective criteria for what changes count as stimuli and what are just "meaningless" interactions with the system.
Information informs about certain details, a system can take the information and understand its meaning. -> I agree that a system which computes can take the information and act in a way that depends on it, but what do you mean by "understand"?
Act in a way that is appropriate to what the information is about. and btw this is an imprecise and vague description of 'understand'. a proper theoretical account would be a lot more precise.
sometimes people use this notion to distinguish between 'data' and 'information' that is more meaningful, like the sort of information that humans can process. -> This is not a definition of either term I asked about.
these aren't my terms/notions. if you really want to know what people mean by them there's stuff online.
Yes, asking what the nature of computation is requires a definition of computation in order to be a well-posed question, but the whole song and dance then reduces to asking about the nature of things that fit some chosen definition (and any definition suffices for playing that game).
If you want to learn anything substantial, you'll generally have to pick some particular model of computation to study. You could choose to study deterministic pushdown automata, and then you will learn about computation that fits in that model. Or you could study Markov algorithms and learn about computation that fits in that model. Or you could even study something like Turing machines augmented with halting oracles. For computers that fit a particular model, you can discover things like what they can and can't compute, how quickly they can compute various things, what it takes to convert a computation system defined in that model into another model, etc., and this will all follow from properties of the model you've chosen to study.
The only thing common to all models is that they have some way of mapping "input" to "output" via some change in "state." That is not specific enough to draw much further insight, so computation theory tends to talk about particular sets of models (e.g. "anything equivalent to a Turing machine").
On what grounds?
The fundamental problem here is that any definition broad enough to encompass everything that can be considered "computation" is going to be too broad to say anything meaningful about the nature of the class of phenomena it describes.
This is a matter of understanding how the phenomena work, not a matter of definition. Can you imagine someone 500 years ago saying "any definition of matter broad enough to encompass everything that can be considered 'matter' is going to be too broad to say anything meaningful about the nature of the class of phenomena it describes"?
But it wasn't a matter of "defining" matter, it was understanding how it worked, and the sort of understanding of matter we have these days -- at the level of protons, neutrons, and electrons, or deeper ones that that -- is very broad, yet very precise.
If you want to learn anything substantial, you'll generally have to pick some particular model of computation to study. You could choose to study deterministic pushdown automata, and then you will learn about computation that fits in that model. Or you could study Markov algorithms and learn about computation that fits in that model. Or you could even study something like Turing machines augmented with halting oracles. For computers that fit a particular model, you can discover things like what they can and can't compute, how quickly they can compute various things, what it takes to convert a computation system defined in that model into another model, etc., and this will all follow from properties of the model you've chosen to study.
It's entirely valid to investigate a particular model of computation as a means of better understanding computation. However, there's a really big danger in such an approach. If there is an underlying unity to the various types of computation, then investigating the specifics of a specific form of computation is likely to make you miss the forest for the trees. That is, if you're goal is to understand computation in general then you need to look at what is there in general, not what is a matter of just one specific way to do it. I do think that in order to understand computation its useful to look at the various forms of it, but to do so with an eye to what is fundamental and general across all the cases.
The only thing common to all models is that they have some way of mapping "input" to "output" via some change in "state." That is not specific enough to draw much further insight...
Why do you think that? You don't say. I think that's an important hint about what computation -- all computation -- is doing.
(and FWIW, this is not a question about 'models' but about computation.. which is always a physical process. 'models' are a kind of computational device that can be used to perform that process).
They are, however, central questions in the philosophy of computing.
Those questions may be considered philosophical now, while they are not understood, but what happens once they become understood (presuming that happens)? Say we had a precise understanding of what computation was - wouldn't that become a central theoretical part of computer science?
For example, I once worked for a distinguished engineering professor who told me about he started his career building simulation models of fluid flow using hydraulic analogue computers. Note that they constructed mathematical models of the fluid flow and then solved these using hydraulics - it wasn't an attempt to simply copy the "real" systems being modelled into an idealised experiment. In this case the fluid in the simulation was arguably "computing" in the sense you mean - but there was nothing that looked like a digital computer or a program or even an algorithm.
In this case the fluid in the simulation was arguably "computing" in the sense you mean - but there was nothing that looked like a digital computer or a program or even an algorithm.
I would suggest that you need a solid understanding of what computation is in order to properly answer the question of whether that case really is the same, in a fundamental sense, as more familiar computation, despite these (perhaps) superficial differences.
I can see at a philosophical level the question is of interest - but arguably at a practical or theoretical level the question is either irrelevant or can't really be stated.
What it a better understanding of what computation is helped you analyse what was going on in biological information processing?
The thing is, we can't predict what benefit might come from some new theoretical understanding.
Take Quantum Mechanics for an example. All sorts of practical things have come from it, but there was no way to predict what these would be before fact.
So yes, it's an interesting philosphical question - but it's meta to the level that most people are actually interested in.
[NB - I am not a physicist, so take any of my statements about what QM is or isn't with a pinch of salt!]
That's fine, and there very well may be some issues here that are worth investigating that don't just involve figuring out a definition. But your specific questions, "What makes something computation", and "What is it about a physical process that means it is performing computation?", both hinge on a blurry notion of "computation" that needs to be pinned down before they can even be taken on.
Because if we take the first definition of the word from Google, "The action of mathematical calculation", then the answer is pretty trivial: a physical process is performing a computation if the states of the physical system reliably map to the result of a known mathematical operation, no more, no less. Now, we may quibble over what is a useful computation, whether a computation is happening if we don't observe it, etc., and that's the kind of tightening of focus that's necessary to get any answers in these situations. Those tightenings are not implicit in the word "computation".
This is a typical philosophical problem - questions like "what is consciousness?" and "what about a physical process makes it conscious?" may be answered in a straightforward manner by going to the dictionary (google (Define consciousness) -> "The state of being awake and aware of one's surroundings"), but answers along those lines reliably fail to satisfy philosophers because they don't actually mean "The state of being awake and aware of one's surroundings" when they use the word "consciousness", they're using some personal tightening of the term that carries a lot of unspecified baggage (or perhaps they'll hide this baggage in "awake" or "aware", which just shifts the issue). Arguments then ensue about the right definition of the word, the one that matches the "know it when I see it" feeling that each person involved has about it, and little progress is made because nothing is pinned down concretely enough to actually discuss.
For a long time humanity has been interested in understanding what physical matter is, and progress on that has been made by understanding how the phenomena actually works, rather than by trying to define what matter is.
I would suggest that people are assuming that, since there appears to them that there is disparate computational phenomena, asking "what is computation?" must just talking about the definition of a term. But perhaps we just need to get a clearer understanding of these cases and we'll see that there is just the one kind of thing going on in all of them. I don't think anyone has any evidence to suggest it couldn't be like this.