Talk:Hydra

Um, I don't see how the decreasing ordinal theorem applies (at least directly) given that you seem to be increasing the ordinal at each step... --Ørjan 21:27, 31 August 2009 (UTC)

Hm wait I now realized you're only trying to decrease the part after the first tree. Still does not apply directly though, because you have no guarantee that the first tree actually has the largest exponent, and 1 + ω = ω . It might apply if you reorder subtrees in descending order before adding up their ordinals, though. Also, when using f's other than the default you need to specify that the result of f must be a single tree, I think. --Ørjan 21:48, 31 August 2009 (UTC)

The DOT applies directly, because the tree that gets increased is always in the same position in the overall expression, isolating the remaining expression as the part that always decreases in ordinality. As long as the ordinality of all-but-the-isolated-tree decreases every time the instruction is executed, it makes no difference what expression we start with or obtain as the result. --r.e.s. (Talk) 14:47, 1 September 2009 (UTC)

No, that only takes care of my first comment which I already realized was confused. My 1 + ω = ω (as an example) objection and the need to reorder still holds. That is, decreasing the ordinality of a subtree does not necessarily decrease the ordinality of the whole. You need to redefine the combination function for ordinality to be something other than the default non-commutative ordinal sum. --Ørjan 00:15, 2 September 2009 (UTC)

See also http://en.wikipedia.org/wiki/Ordinal_arithmetic#Natural_operations for the commutative addition you probably want to use. --Ørjan 00:22, 2 September 2009 (UTC)

Thanks for catching that -- I was intending ordered addition without making it explicit, and forgot all about it when writing that section, which I've now revised. Also, note that my formulation is slightly different than the ones online in various places, as I assign ordinal 0 to the empty expression e, rather to (e). In effect, there's an "invisible" enclosing bracket around every bracket expression, making the two formulations equivalent. For comparison, see this online article. --r.e.s. (Talk) 04:37, 2 September 2009 (UTC)

Your revised sum definition still fails with ()(())(()) giving (ω + 1) + ω = ω2 rather than ω2 + 1, however, since you are only considering swapping the top pair at each step. Also I still think you need alternative g's to give trees as results. --Ørjan 15:34, 2 September 2009 (UTC)

I've revised the definition of the ordered sum to be consistent with the online paper linked above (although as I noted, my formulation uses ord e = 0). Also, I suspect your comment about the g function is related to my not stating clearly enough that g is supposed to map a tree into a tree (which is what both of the mentioned g's do). To get "hydra game" behavior, the critical thing of course is that g increase the size of the "data" tree, which is not guaranteed merely by requiring its ordinal to increase. However, I'm leaving the definition as-is for now, because I think the ordered sum now guarantees that any size-increasing g is a special case of the more-general ordinal-increasing type. Thanks for all the constructive feedback. --r.e.s. (Talk) 12:57, 3 September 2009 (UTC)

This is not an OISC language. OISC implies a processor (CPU) with fixed size registers. OISC is a synonym of URISK - a processor whose number of instructions is reduced to one. --Oleg 01:01, 1 September 2009 (UTC)

I've added a section explaining why hydra is an OISC. If we wish, for hydra the registers may be regarded as individual bits. However, in my opinion, OISC does not imply a processor with fixed-size registers, but is far more general. --r.e.s. (Talk) 14:47, 1 September 2009 (UTC)

OISC does imply a processor with fixed-size registers. OISC is a CPU fetching and executing instructions with the number of instructions reduced to one. But even if you consider the entire memory to be the CPU, your CPU will have to be doing far more many instructions, to evaluate, for example, parsing and counting. (Note the word Computer in the OISC abbreviation, or read, for example, [1] or [2]) --Oleg 22:45, 2 September 2009 (UTC)

We're obviously using different definitions for OISC, mine being that it's an abstract machine using only one type of instruction with some number of operands, as in the Wikipedia definition. This makes the OISC concept extremely general, with abstract "microprocessor languages" as special cases. --r.e.s. (Talk) 13:13, 3 September 2009 (UTC)

It's probably best to regard hydra primarily as a string rewriting system, so I've revised the article to reflect this. --r.e.s. (Talk) 05:11, 2 September 2009 (UTC)

Without changing anything essential, I've changed the order in which the hydra instruction is interpreted -- now as X(Y) rather than (X)Y. That is, now it's the rightmost (instead of leftmost) tree that gets isolated and used for i/o, while the remaining expression eventually gets reduced to the empty string. --r.e.s. (Talk) 14:47, 1 September 2009 (UTC)