Of course, the solution of listing every single case seems about equally unhelpful. The whole thing leads one to question whether proofs are really the goal of mathematics, or just a useful proxy.
2,169 karma · joined May 25, 2009
Of course, the solution of listing every single case seems about equally unhelpful. The whole thing leads one to question whether proofs are really the goal of mathematics, or just a useful proxy.
(Though admittedly, polynomial compression is pretty good, practically speaking.)
As for Kolmogorov complexity, there are infinitely many distinct proofs, so their Kolmogorov complexity cannot possibly be bounded.
They also bury the lede somewhat. Apparently the KiloCore is a 1.78 Terahertz chip:
> The energy-efficient “KiloCore” chip has a maximum computation rate of 1.78 trillion instructions per second
Edit: they later say it's 1.78 GHz. I guess "trillion" is just a mistake?
C++ behavior is almost certainly more complex than Peano arithmetic.
All psychological facts have physical correlates (in philosophy of mind, this is called "supervenience"). The only limit is our ability to measure things. As our ability to measure our own brains and bodies increases, we should expect to uncover more and more physical correlates of psychological conditions.
The article presents this as an issue of physical vs. psychological, but even stripped of that misconception it's still an interesting article.
If you're interested in connections between relational algebra (and SQL, and databases) and logic programming, you should look at Datalog, which is a restricted subset of Prolog that is akin to relational algebra plus fixed points (transitive closure, for example). In particular, Datalog forbids compound terms (like lists) and recursion in a negated position.
I think Datalog without recursion/fixed-points is precisely as powerful as relational algebra, but I don't have a proof handy.
Of course, all of these are overly broad generalizations, and it's not as if there aren't points of intersection between these different ways of looking at programming languages.
But the kind of stuff you'll see in a book like Types and Programming Languages is super-different in approach from the kind of stuff you'd see in, say, the Gang of Four book, both of which are different again from Bret Victor's approach.
I don't think this is true. Modular addition is commutative and associative. As long as the behavior of overflow is modular (as it is in 2's complement), order shouldn't matter. And if the behavior of overflow is to trap, then it should trap regardless of the order you add the numbers in. I guess if you care about the stack trace you get being the same even under optimizations, then you could argue this isn't a safe optimization. And if the behavior of overflow is undefined, it's undefined whether you reverse the list or not.
Maybe you're thinking of Javascript, which not only doesn't have bignums, but uses floating point even for integers?
The article author doesn't think of his question as a "know it or not" question, but a "you should be able to figure this out" question:
> Here's the first reason why this question is so good: a skilled programmer can map their intuition to code. You can tell at a glance whether a binary tree is symmetric, but beginners will often struggle with a question like this because they approach this problem from a visual/intuitive angle rather than the logical angle.
I think it's a fair criticism to say that, at this point, "reverse a binary tree" is something a lot of applicants will have simply memorized rather than figuring out on the fly. But (to play Devil's Advocate) isn't the goal of the question - to test a candidate's ability to think logically and problem-solve on the fly - a reasonable one?
It seems to me the real problems with whiteboard-coding interviews aren't that what they're trying to test - problem-solving on the fly - isn't useful or valuable, but that whiteboard coding is confounded by so many irrelevant variables: ability to think under pressure, ability to code "in your head" (without an editor, IDE or REPL), memorizing solutions, and so forth.
The article doesn't put forward the idea that we should think more of animals for their sake; it's just saying that our understanding is factually incorrect.
> Like native people all around the Arctic — and all over the world — Greenlanders were seeing the deadly effects of rapid modernization and unprecedented cultural interference. [...] Between 1970 and 1980, the suicide rate there quadrupled to about seven times the U.S. rate (it's still about six times higher).
> Her observations are in line with something psychologists and sociologists think is fundamental to the causes of suicide in Greenland. When communities are disrupted, like Kangeq was, families start to collapse. There's an increase in alcoholism, child neglect and physical abuse, all of which are risk factors for suicide. Later, people who didn't get the love and support they needed as children find it difficult to cope with the routine heartbreak of dating, and a breakup becomes the final insult in a lifetime of hurt.
https://www.haskell.org/hoogle/ lets you search for functions by name, including symbol-named functions like <$> and co.
(You can also search for functions by type, which is a pretty cool feature, but not what you were asking for.)
"Untestable philosophies are pointless" is an untestable philosophy, and therefore pointless by its own standards. This is a well-known problem with logical positivism, which is roughly the position you are advocating.
That is exactly what `&mut` is for. An &mut gives you an "ownership lease" on an object; you own it as long as you have the &mut.
Correct. By using GC and banning free() you avoid use-after-free bugs, but not out-of-bounds accesses.
Out of bounds accesses have to be forbidden in some other fashion; most languages do bounds-checking and throw an exception rather than trying to access the memory and getting a segfault (or, worse, reading some random other object's memory).
Obviously, in no language can the empty program solve all problems. QED, there is no language that is optimal in all situations.
If you want a more useful answer, you should define what you mean by "best in all situations".
A technique can be understood, and still a pain in the ass to use; then it is bad. This is of course subjective, by comparison with other ways of solving the same problem.
Or, a technique can be useful, but too difficult to learn to justify using it on something simple; then it is inappropriate, and should be replaced by simpler, presumably less concise, code. This is of course subjective, dependent on the code's audience (readers, reviewers, maintainers). This is the root of the article's map vs for-loop example: different levels of familiarity with the technique of mapping functions over something.
Do they really mean mainframe computers? If so, that is a tiny and unrepresentative portion of all computer programming. If not, it's a hell of a typo.
This idea of a higher-order Prolog is very interesting! But it's not clear to me how it can be truly extensional without further limiting the language. For there is another reason why Prolog is not extensional: non-termination. As a simple example, consider this program:
q(X) :- q(X).
q(adam).
p(adam).
`p` and `q` are logically equivalent (the line `q(X) :- q(X).` is a no-op; of course a predicate implies itself). But in Prolog, `q` is a useless, nonterminating predicate. This problem is not a simple quirk: provability in even first-order Horn logic is undecidable if you augment it with compound terms & unification (as Prolog does), so there is no general algorithm for deciding Prolog queries.It looks like extensional higher-order prolog should have the same problem. The article doesn't address it, so I'll go read the papers.
EDIT: The relevant research papers on Higher-Order Prolog, if anybody is interested: http://arxiv.org/abs/1106.3457 "Extensional Higher-Order Logic Programming"; http://arxiv.org/abs/1405.3792 in which they extend it to negation; https://github.com/acharal/hopes the implementation's github repo
As a practical matter, how do you detect this kind of "evasiveness", and differentiate it from (say) plain old introversion or nervousness?
For a less trivial example, take "resourcefulness". To a large extent, resourcefulness is determined by access to resources. Continued learning after college takes more than curiosity: it takes a bunch of free time to burn on reading, hacking, debugging, etc. What if the interviewee has been spending their time outside of work raising a family instead?