3 ms·
>> While a computer might find some pattern in a string, it cannot find the best pattern. We might find some short program that outputs a certain pattern, but t
by YeGoblynQueenne 8y ago
>> While a computer might find some pattern in a string, it cannot find the best
pattern. We might find some short program that outputs a certain pattern, but
there could exist an even shorter program. We will never know.
If more programmers -especially functional programmers- were aware of this
limitation, we would have avoided countless flamewars about whose language is
best- where "the best language" is the one where someone has written a program
to perform some task, that is shorter than some other program to perform the
same task in another language sometimes written by another programmer (but
often, the same one).
- jl2718 8y agoWell then I have to ask the opposite question. Can a language be made to maximize the difficulty of all possible tasks?
- im3w1l 8y agoIf public key cryptography turns out to be mathematically sound (as crazy as it may seem the functioning of basically our whole tech infrastructure is based on mathematical conjecture), then we can use that to "preprocess" source files before sending them to say a C++ compiler. The result should be turing complete and basically impossible to program.
- smadge 8y agoIf we accept your premises, it actually encourages the flamewar; if you think you're favorite language is being unfairly maligned by those brevity obsessed functional programmers, then the results in Kolmogorov complexity can give you hope that there is a shorter program in your language you can use as evidence against them. ;) In the real world, there are lots of trade-offs at play when writing programs, and obviously brevity is not the only thing to optimize for. However, I think there is substantial empirical evidence that there is strong correlation between the length of a program and the number of bugs in it.
- TeMPOraL 8y agoI think a good way to avoid this flamewar is to point towards the Turing Tarpit, and ask - where does your favourite language shift complexity? If it's any good, it can't really remove it; it can only shift it from one place to another, making certain tasks easier, at the cost of making other tasks difficult.