To give another data point I don't remember one time during my phd where hours of thinking didn't crumble immediately after starting to write code to validate it (or did survive to live to this day if the line of thought was indeed valid).
I've been in meetings that lasted for days and which were all ultimately invalidated by actually writing matching code which immediately made all the issues in the lines of thought glaring and obvious.
One thing I have found programming helpful for in the thought process, though, is to uncover things that one thinks one has already thought through fully, but where there are gaps of detail one has leapt across without even noticing. Programming tends to reveal those.
> gaps of detail one has leapt across without even noticing. Programming tends to reveal those
Agree. As a hobbyist coder I try where possible to do some conceptual thinking by writing out in English my high-level solution approach, and then start coding, fully expecting to uncover some details I hadn't anticipated in advance. I try to avoid diving right in with a hack. But sometimes I find it useful to start with a quick-and-dirty implementation, especially if I'm learning a new tool or language.
honestly im not sure how sarcastically to take this. you can listen to one day of content and really not absorb any of it. it takes the rest of the week to apply, reframe, doublecheck, internalize.
Totally agree with you about the time to internalise training. That said, the quote was a sarcastic one about a specific training course that one of my colleagues thought had too little content.
I believe the original of this type of quote is "A couple of months in the laboratory can frequently save a couple of hours in the library." This saying is referred to as Westheimer's Discovery.
That is the core difference between academia and business. Any engineer who sits back and stares out the window thinking is reprimanded or even fired by the managers for not working.
Hmm... as an engineer in industry, if I decide I want to take a walk in the middle of the day, I make sure I don’t have any meetings, then I get up and leave. There are a lot of differences between academia and industry, but this isn’t one of them. I can’t imagine working for a company where I was worried about something like looking out a window, or not appearing to be working.
I know a lot of engineers who take walks and stuff and still keep their jobs. As long as they’re not skipping out on meetings and actually getting work done at some point, I don’t think it really matters all that much.
Programming does definetly helps me when i do not understand an idea. For exmaple:
I did not understood why in the Monty Hall problem [1] do i have 2/3 chance of winning if i do change the door instead of 1/2 that my intuition tells me until i wrote it as two functions.
function change() {return random(3) != random(3);} // 2/3 chance
function not_change() {return random(3) == random(3);} // 1/3 chance
Then i also saw that i do get that 1/2 chance of winning if i choose between changing the door and not at random.
This was so much more convincing than math and theory and even explanations with cards and drawings because i could run it in a loop a 1000 times and see the results be close to the prediction.
Really? I also value the evidence that numerical simulations provide, and if I didn't know of the problem at hand, the simulation would indeed convince me of the correct answer. But has one really understood something just because one has become comfortable with its behavior?
I would say it was more so the process of implementing that same logic forces you to understand it, and then seeing that logic pan out is a confirmation of what was learned in implementation.
Much like you can understand the math of a lever and see levers working, but precalculating that x can lift y with a z long lever, and then building it, reinforces the logic you used in precalculation and binds the abstract to the real.
I was able to predict how simulation would go when i saw the program that i wrote. When i saw the simulation confirm my prediction it was so much more convincing then any other method. If the logic was to complex for me to understand then i would only see the behavior and not much more.
The Monty Hall problem is typically not clearly explained with the confounding precondition that the game show host won’t open a door that reveals the prize. Once I understood that there was a bias against one of the doors, the problem became obvious.
This is a fairly common reacton to the puzzle these days.
In the time and place of the problem's first widely-distributed posing (Parade Magazine, 1990) it might reasonably be assumed that many people seeing it there were somewhat familiar with the game show it is loosely based on.
Even without that background, one might reasonably deduce that the second door opening never reveals the prize, as there would be no point, in that case, in asking whether the contestant wants to change her pick.
That is a somewhat meta argument, in that it involves understanding human intent and what makes for a good puzzle, and it means that it is not just a math/logic/probability challenge, but it is nevertheless a good puzzle. There's no law that says a puzzle must explicitly state every fact of the matter.
I agree. I think a lot of these probability puzzles end up being "illusions of emphasis", ie., that we fail to grasp the problem because how components of it are expressed in language.
When the host opens the door and why need to be repeated several times and with lots of emphasis before asking the question. These ordinarily minor details are extraordinarily relevant, and the language used should express that.
Yes, because if the problem was expressed purely formally from the start, there could not possibly be any controversy. The appeal of Monty Hall is precisely this interplay of natural and formal language.
It doesn't matter if there's a bias against one of the doors if you're only considering the cases where the door Monty opened did happen to reveal a goat. In two thirds of those cases, you can improve your choice by switching. It doesn't matter if Monty knew the goat was there ahead of time or not!
I was going to make a lengthy logical argument, but I started to wonder if maybe I was reasoning incorrectly as I tried to prune the redundant cases, so instead I took two minutes to write this Python program to enumerate all 27 equally probable possibilities; if you pipe its output to sort | uniq -c you will see that I am correct:
xs = [(you, monty, car) for you in range(3)
for monty in range(3)
for car in range(3)]
print(xs)
for you, monty, car in xs:
if monty == car:
print("Monty revealed the car, too bad")
elif you == car:
print("You win only if you do not switch")
else:
print("You win if you switch")
Now I realize this is dumb because I wasn't excluding the cases where Monty opens the door you picked. Excluding those cases takes us back to 50:50! So I guess it really does matter that Monty knows in advance where the goat is...
How embarrassing that it took me two minutes to get the wrong answer and two hours to realize it — just long enough that I couldn't delete my confident assertions above :) This probably forms some kind of evidence about the quality of evidence you can get out of computer experiments without careful thinking :)
The trick to understanding the Monty Hall problem isn’t to run it 1000 times, it’s to imagine it with 1000 doors. Thinking about the problem with an arbitrarily large number of doors make the solution intuitively obvious. No code required.
This trick did not help me. Intuition told me in the end i have to choose between 2 doors and the chance of winning is 1/2. And it is if i choose in the end at random. This is what made the question confusing for me.
The opening of doors prior to having you make your decision is a red herring. The person opening the doors knows which one the prize is behind, and they’re only going to open doors which have no prize. So if there’s 1000 doors, you have a 1/1000 chance of choosing the correct door, and there’s a 999/1000 chance that the prize is behind a different door. So if the host selectively opens 998 losing doors, leaving your original selection and one other door closed, there is still a 999/1000 chance that the prize is behind the door you didn’t choose. If the host instead opened the doors randomly, there would be a 998/1000 chance that they’d reveal the prize before narrowing it down to the two doors. But they don’t open them randomly, which is why the door opening doesn’t matter. You’re effectively being given a choice between the one random door you originally chose, or every other door.
This was not what bothered me. I needed to see how this puzzle does not contradict my intuition that if i flip a coin to choose between two last doors i do get 1/2 chance of winning whatever are the chances for each door. So with 1000 doors: (1/1000)/2 + (999/1000)/2 = 1/2 chance of winning. And in general (A+B)/2 = 1/2 if A+B=1.
If you flip a coin at the decision stage, then you would have a 50/50 chance of winning. But that approach would mean you’re disregarding information that you can use to increase your chances of success above 50/50. When you make your initial choice you have a 1/1000 chance of guessing correctly, meaning there is a 999/1000 chance that the prize is behind another door. By eliminating 998 doors from contention, you’re not changing those odds. There is still a 999/1000 chance for the prize to be behind a door other than the one you initially picked. Only now, instead of having 999 doors to choose from, you only have one. So by switching your choice, you increase your chance of success from being whatever it was initially, to being (1 - whatever it was initially). Which will always be greater than 0.5.
This is materially the same as being given a choice between opening one door randomly, or being able to open every other door. Because the conditions of opening doors prior to the final choice is that the door you initially picked can’t be opened at this phase, and neither can the winning door.
Yes! This was how I first figured out how to understand it, and how I explain it to anyone if it comes up. It's immediately obvious with a large number of doors.
Yeah, the use of 3 doors, and the bit where one is opened just kinda hides what’s happening. Which is that you’re actually choosing between one random door, or ALL the other doors.
The Eureka moment for me was similar, but slightly different. Consider a variant game with N doors. You pick a door, then Monty offers you two switch your payout to "the best single result from the remaining N-1 doors". Clearly, you would swap.
Now set N to 3, and consider that, by opening a door without the prize, that's exactly what Monty's offering you.
Maths is not experimental. This roundabout, handwavy, vague way to deal with things causes more harm than good, in my opinion. Try to understand a proper mathematical proof instead.
> A computer is used by a pure mathematician in much the same way that a telescope is used by a theoretical astronomer. It shows us "what’s out there."
> From such explorations there can grow understanding, and conjectures, and roads to proofs, and phenomena that would not have been imaginable in the pre-computer era. This role of computation within pure mathematics seems destined only to expand over the near future and to be imbued into our students along with Euclid’s axioms and other staples of mathematical education.
I disagree. Math is very experimental - it is bottom up science where you first touch various details in the dark and generalization comes later.
I am with Arnold on that.
> Arnold was an outspoken critic of the trend towards high levels of abstraction in mathematics during the middle of the last century. He had very strong opinions on how this approach—which was most popularly implemented by the Bourbaki school in France—initially had a negative impact on French mathematical education, and then later on that of other countries as well.
This roundabout, hand-wavy, vague way to deal with things is how mathematicians solve problems. You have to have an intuitive understanding of what's going on before you can formalize the solution into a proof.
I majored in math in undergrad, and one of the required courses was about communicating mathematical ideas. One of my bigger projects in that course was to explain the Monty Hall problem so it could be understood by the general public, and I got a good grade by putting together a lesson plan that included this type of simulation.
Math is experimental at its roots. If the result here wasn't usable in real life, scarcely anyone would develop that specific branch of probability theory.
Instead they would think of adjusting the axioms and work out a useful probability theory.
For example, most children check 1+2 experimentally before accepting the theory.
Not the GP, but this is my take on their comment. Children learn counting before they learn an algorithm for addition. The "theory" to accept here is that counting a set of size x, then continuing to count, starting from x, a set of size y, yields the same result as the addition algorithm for x+y that they learn.
I think he means loosely that the theory here, is that they add up to three. Kids will grab objects and group and ungroup them while counting and so on, before outright accepting math is real.
I consider myself borderline math illiterate. I understand the monty hall problem perfectly well through means other than hard math proofs.
So, clearly, understanding the proof isn't required. It is a great deal more work than many other methods of understanding the problem, so why prescribe it as the best way?
You might be comfortable with it, but not everyone has the time nor inclination to become mathy enough to live life through your lens.
I know this is a favorite idea that is often quoted. But as a plodding person doing research in CS, I don't find that programming enhances big-level understanding. It may refine some of the nuances one does not notice in the first pass, but after a tiring debugging session, I don't usually find any flashes of insight about the overall problem.
An example: rotation and balancing of binary trees - does battling the inevitable core dumps during implementation really enhance any understanding of the principle of the algorithm?
In my experience, it's easy to be hand-wavy about the details of algorithms without even realizing it. Programming forces a level of rigorous thinking and, importantly, allows you to get feedback from the machine.
A recent example I went through as an exercise was writing a regular expression engine. I understood the desired behavior and the theory of finite automata (or thought I did) but in programming it I was forced again and again to review the concepts and proofs in a very detailed and rigorous fashion.
One last thing I would add is that I agree that language- or machine- specific details can get in the way of high-level understanding; this may be inevitable to a certain extent but choosing a language that fits the abstraction level of the problem helps a lot.
If your goal in implementing rotation and balancing of binary trees is to better understand a poorly understood idea then you're probably better off using a language like Haskell that is garbaged collected and doesn't have nulls so you can both avoid having any core dumps and also have a smart compiler to help guide you to the solution and the understanding.
I think it helps in physics because you very quickly condense a large number of different mechanical situations into basically one numerical integration problem. Students quickly are able to calculate anything forces related and are able to see how every class of mechanics problem is basically the same problem. This is difficult traditionally because the mathematical tricks, such as rotating coordinate systems, take over the physics.
> An example: rotation and balancing of binary trees - does battling the inevitable core dumps during implementation really enhance any understanding of the principle of the algorithm?
It can especially if it is your first time learning about AVL, red black trees, etc. The process of implementing, debugging, etc can help you understand the algorithm and its underlying principles. Even more it shows you the practical merits and limitations. There have been times when I thought I understood an algorithm or data structure until I had to code it and then realized I didn't really understand it.
But generally speaking, you don't need programming to understand "big-level" stuff in CS no more than you need a pen and paper to understand mathematics. Church and Turing didn't program and they helped create computer science.
You're correct, it's better to know the algorithm on paper before starting to program it.
An extreme example of that is MySQL's InnoDB. It was written by 4 math PhDs who focused on rigor and correctness, which is why InnoDB is one of the most outstanding codebases in Open Source. The Internet basically runs on InnoDB.
Having said that, programming experience will make you more logical over time, which can help with analysis.
Sure, you're right about safety and conciseness. But C/C++ implementations maintain fidelity to the complexity analyses found in the algorithm literature. Amortized analysis in Okasaki-style OCaml implementations does not really compare to amortized analysis in lazy languages like Haskell, and all of these are quite different from the regular pointer-based implementations.
I think perhaps the real safe alternative might be Rust.
> But C/C++ implementations maintain fidelity to the complexity analyses found in the algorithm literature.
Not in any meaningful sense. On modern hardware, the dominant factor affecting performance is cache efficiency, and that's not at all visible in C/C++ code. So you're not really any better off in C/C++ than you are in OCaml (to use your example): the asymptotics are valid, but you have no idea (without resorting to reasoning about compiler and CPU internals) when a small change is going to cause aliasing or blow out the cache and lead to an order of magnitude performance difference.
But at least in C/C++ you can fix it. That is, I can control how my data lines up with the cache in C/C++, with sufficient care and effort. Doing the same thing in Haskell or OCaml would be considerably harder.
> That is, I can control how my data lines up with the cache in C/C++, with sufficient care and effort. Doing the same thing in Haskell or OCaml would be considerably harder.
Would it really? The OCaml compiler is pretty simple and consistent; there was a story here not so long ago where some OCaml users diagnosed a CPU bug that people using C/C++ hadn't noticed.
I don't know if the problem is that you don't know OCaml or that you don't know C, but yes, it is considerably harder; in OCaml you cannot embed objects in other objects as you can in C (and C++, and Golang), because OCaml uses the Lisp memory model, as described in http://canonical.org/~kragen/memory-models. Consequently you end up with things which are perhaps conceptually a single object potentially strewn around the heap at random, however the allocator and the garbage collector choose to arrange them, and linked together by pointers. There's a lot of payoff for this — it's safe and trivially easy to write parametrically polymorphic code in OCaml, while it ranges from fiddly and error-prone to overwhelming to impossible in different languages in the C family — but it's a major fundamental difference, and it does have some runtime efficiency costs.
Where do I find a language free of bugs, vulnerabilities, and anything else that may impact security, while being able to develop things at a sane pace?
According to Curry-Howard correspondence, writing programs is like writing proofs. So a working (or at least type-checked) program is like a proof that was verified by the computer.
In that sense, the poorly understood ideas have to be expressed more precisely, when writing a program. The program itself, however, is not necessarily a good medium to express the most interesting ideas, because they can drown in technical details.
The "propositions" that are proved in anything but dependently typed languages are trivial though, so Curry-Howard is not that relevant in this context. E.g. a program of type "Int" merely proves that the set of integers is non-empty, and it doesn't even prove that for languages that are Turing complete (as the "proof" may crash)
That's why I used phrase "working program" and "verified" in my comment. ;-)
If you have a working (tested) program, you might not have a mathematical proof that it works, but you have certain sense that what you're doing is not entirely logically implausible. It is a form of verification (although without complete guarantee of correctness).
(Another way to look at it is that the testing you did determines what kind of sentence you proved to be true. So instead of assigning the type to the program in advance, you deduce it the other way around - we observe how the program works and that gives us its type.)
Just because the program corresponds to a proof, doesn't mean it proves anything interesting. It may not give any insight into the subject you're trying to understand
Yeah, that's why I call bullshit on Curry-Howard. It's really not that important or noteworthy. Writing down a program is not like writing down a proof. It is like writing down a specification.
This is how I'm modelling things that I'm learning. I'm defining types (in Haskell) and functions that map those types to other types. Even if I don't write the implementation of the functions, that still gives me a clearer idea of the domain.
I once attended a fascinating presentation where the presenter had realized that since laws were written in a specialized legal language, that this could be used to write proofs and discover inconsistencies and errors in the law.
