Hacker News Reader

Are you sure the constant is enormous? https://arxiv.org/abs/1606.00484

The paper you've posted: "The Median of Medians (also known as BFPRT) algorithm, although a landmark theoretical achievement, is seldom used in practice because it and its variants are slower than simple approaches based on sampling."

Me: "It's O(n), but the constant in the front is enormous, so it's usually totally impractical"

?

But it is not impractical!

Quickselect is trivial to write and has a much better constant on average, but can be O(n^2).

If you do rounds of quickselect then occasionally a round of median of medians, you get guaranteed O(n) performance that on average is as close as you want to what quickselect does.

I'm not saying QuickSelect has a large constant. I am saying the median of median O(n) algorithm, which again is not QuickSelect, has a large constant.

And I am saying that when you combine the two you get an algorithm with a small constant in practice and guaranteed O(n) behavior in the worst case.

For example do quickselect on 9/10 rounds but on every 10th round do a median of medians. The overhead of guaranteed performance will only be a few percent off of the average.

That's very cool. However, the anecdote I was sharing for comparison purposes specially referred to the median of median algorithms. This was also many years ago, long before the paper above was written.

I'm not saying that it's impossible to do it and always will be. Re-read what I've said if you like, and you'll see I am simply sharing an anecdote for the purposes of an analogy about this particular situation.

This didn't make intuitive sense to me so tried to Google it. Is "Introselect" what you're referring to? https://en.wikipedia.org/wiki/Introselect

It's a hybrid of quickselect and median of medians, but the switching strategy's a bit more complicated.

Introselect is a more complex version of the same idea.

But basically both quickselect and median of medians are divide and conquer. Median of medians is an expensive way to guarantee a good division. Quickselect hopes for one.

If quickselect goes well, then median of medians will be relatively cheap when run because it is run on a much shorter list. If quickselect does not go well, the median of medians passes guarantee progress. So average behavior is only slightly worse, and worst case behavior is still nicely bounded (albeit with a much worse constant).

I remember my algorithms class wasting like a week and a half going over that. I'm still a little bitter. There's only a few courses that I would have wanted a refund on my tuition for, and that's one of them.

I'm not a domain expert, but I would assume that "approaches based on sampling" could be O(1). If so, the slowness would be based on the scaling, not on the constant.

If you keep the number of samples constant (so that you can have O(1) time) then the quality of the estimate goes down with the number of items in the collection. To keep the quality constant, you need number of samples to scale with the size of the collection.

Depends on how you are measuring accuracy.

Suppose I have a set of all integers less than k and > 0, and you after N random selections want to estimate k. Presumably as k increases your accuracy drops in absolute terms. But, if you do the same thing using the reals so there is infinite number of numbers from zero to k you can still make a bounds for k.

Granted there are now infinite number of reals in your estate, but you can still pick an N such that an arbitrary % of the time k is +/- an arbitrary % of your guesses.

Not necessarily, using k samples you can estimate the mean of i.i.d. samples with a variance of 1/k the sample variance. Note that this is independent of the sample distribution, in particular it's also true if you're drawing from some fixed collection, regardless of its size.

I find it harder to say something about the median, but I imagine some similar theorems hold.

Unless you have some definition of quality for which you can show that you do need more samples with a bigger collection?

But the constant is not large. O(n) quickselect is extremely fast algorithm.

Quickselect has an O(n^2) worst case, unless you use a variant like Tarjan's median-of-medians algorithm for selecting the pivot. And that does have awful constant factors.

Yeah, this was the specific algorithm I meant. O(n) time, but in my undergrad implementation, it wasn't useful with less than billions of items, vs just sorting and selecting with highly optimized sorts.

If you are dealing with numbers, then you can do this is true O(n) time with radix-select. (Basically do a MSB radix sort and only do subsequent passes in the bucket where you know k must be).

Wow. can't believe no one ever mentioned this before, Most Significant Bit bucketification would cut down seek time a lot.

Oh, you should have seen my implementation then.

There are two types of algorithms . Ones we can implement with reasonable time. Then the others where we can’t implement in a reasonable time at this moment.

Have you ever heard of an omega or theta bound?

I might have - give me a minute to check the owner's manual for my hypercomputer.

Reasonable is relative.

Ya, the obligatory pendantics (concern trolling, nit picking, Eeyore-isms) is frustrating. I have a core group of nerd friends that are fun to play catch with. Any more, I’ve stopped voicing my crazy, weird, random, fun ideas to most people.

"Concern trolling" is a behaviour I've always noticed but could never describe.

Mainly related to jealousy in my experience, with people trying to detour you with a myriad of concerns

Well, the proof is contrived, but that's not the point: it's also unnecessary and it may also be insufficient.

To claim a system is Turing complete, what you need is (a) a store, from and to which you can read and write; (b) branching (if-statements); and (c) the ability to repeat instructions an arbitrary number of times (while-statements).

It's easy to show that M:tG has all of the above: the Stack is a store; you read from and write to it when you place abilities on and resolve them from it. Branching and loops are present in ability text sentences like the following:

You win the game if you control a land of each basic land type and a creature of each color. [1]

When you cast this spell, copy it for each spell cast before it this turn. [2]

As to a demonstration that the system actually works- you can point to any M:tG game.

Finally- the proof in the OP may not be general enough. It uses only a limited sub-set of M:tG cards, so the best we can tell is that that specific sub-set of M:tG cards is Turing complete. For a more general proof, you at least have to explain why a specific subset is chosen and explain why you can substitute it with any other subset without loss of generality.

The problem is that "card" is not a granular enough unit of the M:tG game to define as a symbol of an alphabet. A really general proof would make use of tokens of the ability text language. Such a proof would hold for any set of cards.

___________

[1] Coalition Victory: http://gatherer.wizards.com/Pages/Card/Details.aspx?multiver...

[2] Storm keyword ability; e.g. Dragonstorm: http://gatherer.wizards.com/Pages/Card/Details.aspx?multiver...

A formal system, in this case the game, is Turing complete if it can be used to implement a Turing machine. Complaining about using only a limited and very specific subset of available cards in a contrived way is like saying that a computer is not a computer because a large number of transistors aren't part of it, and if I rewire it randomly it ceases to work.

Regarding "unnecessary", unlike typical competitive or recreational games in which players often do what they want, this particular setup results in an automaton in which players cannot disrupt the operation of the Turing machine:

"The idea of my Magic Turing machine is that the players do nothing at all, except when the game offers them a choice."

The article explains that the setup only allows choices to do optional actions, and it is assumed the players always do them. As "programming" human players to simulate a Turing machine would be too easy, they are replaced by mindless placeholders.

If you used humans, they could follow the rules in their head (with written reference sheets); tapes could be lines of objects belonging to an alphabet of different types (e.g. coins of different countries and denominations, Barbie dolls of different model years, wax crayons of different colours), and the machine head would move by walking in front of the next tape position. No need to involve a proper formal system like a card game.

>> The article explains that the setup only allows choices to do optional actions, and it is assumed the players always do them. As "programming" human players to simulate a Turing machine would be too easy, they are replaced by mindless placeholders.

Yes, I read that bit - I didn't realise it was meant to make things "harder". That alone is good enough to convince me the proof is unnecessary. If you can make a proof easier, then you make it easier. There's no need for harder proofs.

Also, the fact that the proof does not involve human actions is another piece of evidence against the generality of the proof. You can model human choices as a distribution and allow for a fully-automated proof, that doesn't require human input in the strict sense. But leaving human actions out of the proof makes it less general- because the full game does involve such actions.

For Turing completeness it is not sufficient to demonstrate that a system has "a store". The store needs infinite capacity and random access. Infinite capacity alone is not enough - a stack has infinite capacity but a stack machine has demonstrably weaker expression power than a Turing machine: https://en.wikipedia.org/wiki/Pushdown_automaton

Same goes for if-statements. The statements need to be general enough and work with the rest of the system to be usable to express the Turing machine. In particular your example of an if statement that starts "you win the game if..." makes this statement sorta useless, as it ends the computation. You can't make a Turing machine if every "if" ends the program. Same goes for any other "if" in the rules - they are usually pretty limited.

"As to a demonstration that the system actually works- you can point to any M:tG game."

Again, that alone is not sufficient. It only proves that the system works for expressing one kind of computation, namely MtG games. For Turing completeness, you need to demonstrate that any Turing machine computation can be expressed as an MtG game, which is what the linked proof does.

There's no limitation on the size of the M:tG Stack, so it is infinite. Also, that M:tG uses a Stack as a store doesn't make it a pushdown automaton. For a pushdown automaton you need the stack to control decisions, but that is not the case here- there's still player actions and the effects of cards in the game etc.

The if-statement I quoted is just one example. The following does not end the game:

At the beginning of your upkeep, draw a card if you control the creature with the greatest toughness or tied for the greatest toughness. [1]

The important thing to note of course is that the above are well-formed sentences in the ability text language. So the language allows if-statements and it doesn't matter how many cards with if-statements are actually printed.

Also, strictly speaking, winning the game doesn't necessarily terminate processing. The ability of the card Shahrazad [2], for instance, creates a sub-game that may end without ending the original game:

Players play a MAGIC subgame, using their libraries as their decks. Each player who doesn't win the subgame loses half his or her life, rounded up.

Like I say, if you can show that the system has the components it needs to be Turing complete, then you've shown that it is Turing complete. Simulating a Turing machine is just another way to show Turing-completeness.

_______________

[1] Abzan Beastmaster, http://gatherer.wizards.com/Pages/Card/Details.aspx?multiver...

[2] http://gatherer.wizards.com/Pages/Card/Details.aspx?multiver...

"The language allows if-statements and loops" is not sufficient for the language to be Turing-complete. A language with loops in which the only form of selection is "if 4 > 3 then…" is not Turing-complete. Just pointing to a specific if-statement appearing on a card and saying "yeah, that's probably enough to make Magic Turing-complete" does not constitute a proof.

I think you might be confused by the term "language". In the context of the proof, "language" means "anything that is the Oracle text of a card". You seem to be using it as "anything that could be printed on a card". I think you're saying "the game of Magic-but-where-I'm-allowed-to-choose-what-the-cards-say is Turing complete", which is undeniably true but also not the point.

Yes, that's exactly what I'm saying- why is it not the point? If you were trying to prove that Java is Turing-complete you wouldn't look at all the Java programs ever written and try to build a Turing machine with those programs. Instead, you'd use the symbols in the language to write a (new) program that simulates a Turing machine, or a set of functions that suffice to prove Turing completeness.

The proof the author has given is equivalent to building a Turing machine out of existing programs in his language of interest. M:tG cards have instructions printed on them in the ability text language - so those instructions, rather than the cards themselves are the symobls in the language. The cards are best seen as scripts or small programs written in that language.

But why should anyone restrict themselves to existing cards when trying to prove the Turing completeness of the language?

Note, also, that the rules of well-formed sentences in the ability text language are given in the M:tG Comprehensive Rules or at least some of them are- there's no complete formal definition of the language. Still, there's plenty enough for anyone to be able to form syntactically correct ability text.

So, again- if you're trying to prove the Turing completeness of a language, why would you not use the full expressive power of the language to compose new strings? And instead restrict yourself to just a few pre-existing strings of it?

The game of 'Magic: The Gathering' consists of both the rules and the cards available in it (which are written in a kind of language). If you are printing your own cards, most players would agree you are not really playing 'Magic: The Gathering', but your own homebrew game based on it.

Maybe, but if we're doing formal proofs then we're not in the realm of opinion anymore. So the point is to substantiate any claim as to what, exactly, is reasonable to call "the mtg language". I really doubt there's any context in which a language can be formally described as "a limited number of texts"... especially if that language is supposed to be Turing complete (which implies non - finite-ness) !

BTW, the kind of language the ability text language is, has a name: it's a Controlled Natural Language. [https://en.m.wikipedia.org/wiki/Controlled_natural_language].

As to the relation between the language and the rules, if you think about it, if the language is not equivalent to the rules, then it can't represent (and, therefore, modify) every rule in the game (as it is supposed to). And if the language and the rules are equivalent, then proving one is Turing complete also proves it for the other. So you can ignore the rules and focus any proof on the language.

Just to make it plain. In formal language theory, a language is a set of symbols and a set of rules that determine what is a valid string.

Given such a definition of the ability text language, you don't need to restrict yourself to only those strings that are actually printed on cards.

In the same sense, we don't define the English language as every text ever written in English - but as some unknown formal system that can produce an unknown, probably infinite, number of strings that includes all text ever written in English.

So why treat the M:tg language any different?