Could you support your claim that running times are irrelevant? I understand you want to keep your blog post (or "blarticle") short. But maybe you could elaborate here? I am genuinely interested in your argument.
I think there are other caveat of specifying only the results.
That post also contains a statement which I believe to be false. You state that the "Haltability problem" (where you are given a program P and want to determine if there exists an input on which it halts) is decidable but its not.
Basically, I can just hardcode any input I of my choosing into P so that it always does the same thing (run P on I) regardless of the actual input I' you provide it. Thus, I can use an algorithm for the Haltability problem to solve the halting problem.
I know that does not pertain to this post directly but the halting problem does. Given a program written in this new language, how can you determine if what the programmer specified can even exist as a program?
In fact, suppose you specify the properties of this new language you current wish to construct (in say, English and assume that everything is interpreted correctly). How do you know such a language could potentially exist (never mind implementing it)?
I also don't even want to think about debugging in such a language. More specifically, I would rather have a library for the example you described because if I make a mistake in my specification, I have ways to find the error in it. But I guess this goes back to my previous question: what does your compiler produce on an incorrect (or outright impossible) specification (i.e., piece of "code")?
Its certainly interesting to read about thoughts on potential new languages but I wish there were more solid theoretical foundations for posts like these. Otherwise, I feel that the same energy would be better spent on improving existing languages with some subset of the features you want.
Not to discourage you from trying anything but it looks like you've ignored the complexity issues with this (I won't pick at the fact that you described an O(n^2) algorithm for sorting).
I understand that you don't want to specify the steps to achieving the goal but the steps directly impacts running time.
In your particular example, a compiler could produce a program with the correct output but runs extremely slowly even for small arrays (by simply trying all permutations until it finds one satisfying your constraints, or even worse, randomizes the entries until the constants are satisfied ("bogo sort")).
Furthermore, there are undecidable problem for which the output is easy to specify but no program could exist. For example, deciding if an input piece of code will loop indefinitely.
In your article, you've mixed needless overhead (the dummy/local swapped variable comes to mind) and the steps needed to specify an algorithm.
If you only want to remove the overhead (and thus, some source of mistakes you've pointed out), you could aim for a language where the algorithms are easier to specify.
In the bubble sort case, the code would look something like.
def bubble_sort( array ):
while there is an i such that array[i]<array[i+1]:
swap( array[i], array[i+1] )
(You can almost do this in Python already which seems to be where the syntax is inspired from. I can elaborate if interested.)
Ultimately, I have to agree with other comments saying this will be more useful for checking than specifying a program.
This sounds like an interesting topic, but the article itself was more confusing than enlightening to me.
It seems that the actual explanation (using Hamming distances) could be used instead of the bubble-wrap analogy (in the same amount of space, without making more assumptions about the reader). I felt it didn't represent the trade-off (or rather the strict improvement in this case) very well. In fact, it seems to suggest something that is false (that the two methods are fundamentally different).
They also start using graphs without an (informal) definition.
I didn't know about tree codes before so this could have been interesting but I still don't know much about them. The article alludes to some kind of uniqueness theorem
but remarkably Leonard showed there is actually one out there that’s useful
but the end suggests that we do not actually know the optimal strategy (so I guess its just an existence proof?).
a set of structured binary strings, in which the metric space looks like a tree,
doesn't tell me much either. How should I interpret "look like"? Do I approximately embed the space in R^n? Do they mean that its close to a tree metric?
Finally, the article also didn't mention how little we actually know about, say, the Shannon capacity of many (small) fixed graphs. The impression I got is that we already know all there is to know about "classical" Shannon capacity (which I believe is false).
I think there are other caveat of specifying only the results.
You posted earlier on the halting problem
http://evincarofautumn.blogspot.com/2011/10/solving-halting-...
That post also contains a statement which I believe to be false. You state that the "Haltability problem" (where you are given a program P and want to determine if there exists an input on which it halts) is decidable but its not.
Basically, I can just hardcode any input I of my choosing into P so that it always does the same thing (run P on I) regardless of the actual input I' you provide it. Thus, I can use an algorithm for the Haltability problem to solve the halting problem.
I know that does not pertain to this post directly but the halting problem does. Given a program written in this new language, how can you determine if what the programmer specified can even exist as a program?
In fact, suppose you specify the properties of this new language you current wish to construct (in say, English and assume that everything is interpreted correctly). How do you know such a language could potentially exist (never mind implementing it)?
I also don't even want to think about debugging in such a language. More specifically, I would rather have a library for the example you described because if I make a mistake in my specification, I have ways to find the error in it. But I guess this goes back to my previous question: what does your compiler produce on an incorrect (or outright impossible) specification (i.e., piece of "code")?
Its certainly interesting to read about thoughts on potential new languages but I wish there were more solid theoretical foundations for posts like these. Otherwise, I feel that the same energy would be better spent on improving existing languages with some subset of the features you want.