7 ms·
Major unsolved problems in theoretical computer science?
- Permit 15y agoReading over these reminded me how poor I am at discrete mathematics. I've taken one class so far, in which I did fairly poorly and I was wondering if anyone had suggestions on where one could turn for practice or learning material for this sort of math/CS theory?
- liuhenry 15y agoMy recommendation is "Concrete Mathematics", by Graham, Knuth, and Patashnik. (http://www.amazon.com/Concrete-Mathematics-Foundation-Computer-Science/dp/0201558025 http://www.amazon.com/Concrete-Mathematics-Foundation-Comput...) 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 http://news.ycombinator.com/item?id=755043 Ask HN: good math books http://news.ycombinator.com/item?id=665029 http://news.ycombinator.com/item?id=665029 Ask HN: Learning advanced math http://news.ycombinator.com/item?id=1753029 http://news.ycombinator.com/item?id=1753029
- Scybert 15y agoHow to not smell.
- jamesrcole 15y agoI see 'what is computation?' and 'what is information?' are not listed there. I'm curious what HN thinks of these questions. Do you think they should be on there or not, and why? 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).
- alextp 15y agoI don't think you can answer these questions with theorems or experiments about models of computation (which is how TCS answers questions), so I don't think they are TCS questions. They are, however, central questions in the philosophy of computing.
- jamesrcole 15y agoI'm know most people think this, but to me it seems narrow to construe TCS that way. There may be theoretical questions you can only answer once you understand clearly what computation is, especially by having a more physical notion of it. 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?
- arethuza 15y agoI'm not sure there is much utility in trying to define "computation" as an intrinsic property of anything in the real world, rather it is a useful property that we can ascribe to particular systems if that proves to be useful. 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.
- jamesrcole 15y agoIn my opinion it's not a matter of definition, it's a matter of understanding a real type of phenomenon. 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.
- deleted 15y ago[deleted]
- dkarl 15y agoOne answer links to a list of open questions in the lambda calculus. All the others are defined in terms of computational complexity. As a math major, computational complexity was the first topic in computer science that caught my interest (as opposed to programming, which I'd enjoyed for years) but I didn't know it was virtually the whole show! Are there open problems beyond complexity theory and the lambda calculus?
- riffraff 15y agohonestly, I have no clue what the boundaries are between disciplines and what lies under the umbrella of "computer science", but I recall many open problems related to distributed systems. Although now that I think of it, those may also have been (re)phrased in terms of computational complexity.