Talk:Eodermdrome

Please post some examples. This is an original language as far as i can tell, but I can't understand it at the moment. Examples would be wonderful. Revcompgeek 03:13, 10 December 2008 (UTC)

I may do some time. The problem is it's also a very hard language to write in, and I haven't got any working non-trivial programs yet. --ais523 10:44, 12 December 2008 (UTC)

I started designing the implementation of SK combinator calculus in Eodermdrome.

But it's not easy. In addition to defining the term encoding and rewrite rules, one needs to define helpers for term destruction (in the case of K) and term duplication (in the case of S). It would be easier to define the BCWI combinator calculus, but that's not even Turing complete IIRC. -- User:atehwa 22 July 2011

Question about the categories

How it can be "Turing tarpit" and also "Unknown computational class"? The definition of "Turing tarpit" requires that the language will be Turing Complete! --(this comment by 77.125.146.64 at 16:02, 25 May 2009‎ UTC; please sign your comments with ~~~~)

(Whistles innocently) Fixed. --Ørjan 16:44, 28 May 2009 (UTC)

Name

The name "eodermdrome", graphed, is itself a clique with 5 nodes. OberoN (talk) 13:46, 26 July 2012 (UTC)

Yes. --Ørjan (talk) 21:35, 26 July 2012 (UTC)

multiple matches

What is the expected behaviour if the internal state graph contains more than one subgraph that's isomorphic to the command's match subgraph? My initial assumption was "replace all such subgraphs", but they may overlap. Should one possible match be chosen in an arbitrary manner? --GreyKnight (talk) 10:54, 16 April 2014 (EDT)

Yeah, the standard solution is just to pick a match nondeterministically. Phantom Hoover (talk) 10:58, 16 April 2014 (EDT)

Looping examples

Here are some examples to demonstrate finite loops in Eodermdrome to help others getting started with this language. Each line is an independent program. They all start from the default thequickbrownfoxjumpsoverthelazydog graph and loop the number of times according to their descriptions. They use the spec's punctuated-whitespace for readability. (I've added that functionality to the python interpreter). All keywords are completely arbitrary, remember: "it's the shape of the graph that matters, not the letters used to define it."! as such, please excuse the grammar. They are graphs, not words.

one. time.  (1 ) once
does. this. (2 ) twice. times. over
and.  this. (3 ) repeat. thrice. over 
this. one.  (4 ) repeat. four
and. this.  (5 ) repeats. five
this. one.  (6 ) repeats. sixes
and. this.  (7 ) repeats. seven. times
this. one.  (8 ) repeat. times. eight
this. one.  (9 ) does. nine. repetitions
and. this. one. (10 ) ten. times. over

Salpynx (talk) 23:49, 28 January 2019 (UTC)

Computational class / ℒ-completeness

Originally I didn't understand how the statement under Eodermdrome#Computational_class "because there are only a finite number of Eodermdrome programs when I/O matching is not considered" could be true, since one could always trivially add more lines to an Eodermdrome source file and therefore have infinitely many Eodermdrome source code files / "programs". Also, the number of nodes in the state graph is limitless, so there are no bounds there.

I eventually understood why after trying to create a counter example: because the number of nodes that can be referenced in any one line is limited to lowercase (ASCII?) labels, and commands are not stored in order and can run any number of times, eventually the number of unique commands in the program memory reaches a maximum. You can always add more lines to the source code, but at that point they will be duplicating already existing rules and therefore have no additional effect. It is true that there are infinitely many possible Eodermdrome source code files, but infinitely many of those are functionally identical. Duplicating rules is equivalent to adding different amounts of whitespace.

This is my attempt to enumerate exactly how large the maximal Eodermdrome program superset is (in unique lines / rules):

 sum(A0013491, ..., A00134926)2

This uses the sequence A001349: Number of connected graphs with n nodes. It assumes lowercase is limited to Latin / ASCII, which is how the two available interpreters work, although I don't think the spec strictly limits that. Replace ₂₆ with however many 'lowercase letters' there are really. This could be off, I was trying to get all possible match:replacement combinations of unique representable sub-graphs. Corrections welcome. I don't think it is feasible to generate this set as code, but it is finite.

In conclusion, I agree that Eodermdrome is ℒ-complete, which seems a subtle concept. I don't think this precludes it being possible to create a bf interpreter in Eodermdrome which has an infinite data tape though, and I'm not sure if that is what "[not] Every Turing machine can be mapped to an Eodermdrome program" implies.

P.S. Note: the above only applies when I/O (specifically Input) is prohibited, according to ℒ rules. With input, you could easily differentiate commands on input matching, and if there was an external clock which simply incremented every tick, you could create a program of arbitrary size with sum(A001349₁, ..., A001349₂₆)² commands for every input integer (i.e. infinite). I'm still trying to figure out the implications of ℒ-completeness, it doesn't seem to restrict anything practical?

Salpynx (talk) 05:32, 1 February 2019 (UTC)

Even without I/O, I think it's much more complicated to calculate. A replacement cannot be specified just by two unlabeled graphs, because the open nodes have identity that must be preserved.

On the other hand, if you add input, that is by single characters, not integers, so you don't get an infinite number of programs that way. --Ørjan (talk) 20:34, 1 February 2019 (UTC)

You are correct about reading single characters, my mistake! I had assumed input was to EOL and multicharacter input matching was possible, it's not. I think I got confused because the input set can be more than one character, but it means match on any one of this set. To wriggle out of my mistake, how about an esoteric character set proposal: 'Unicode ∞' a hypothetical unicode extension that provides a code point for all ℤ for this sort of esolang use? Every ℤ has a corresponding 'character', even if it does not have a glyph (yet). I'd need to check there is a way to extend utf-8 continuations beyond 4 bytes without causing problems, or come up with another variable length multi-byte encoding.

For preserving open nodes, my calculation above does include matches with zero open nodes, but I think that's valid. There isn't a restriction that matches must have any open nodes, as far as I can tell. I am only trying to enumerate possible rules, which need only be valid for one internal state graph.

Starting from a connected square of four nodes: thequickbrownfoxjumpsoverthelazydog (START) plorp

a (add an arm) abcd adds new nodes attached to a single existing node, so only one open node is acceptable.

plorp (complete replacement) tint replaces the whole square with a triangle of completely new nodes, so having no open nodes is also acceptable.

a (complete replacement) tint won't work from the 4 connected nodes starting point, because a is closed and has degree 0 so doesn't match any node in the internal state graph.

 thequickbrownfoxjumpsoverthelazydog (START) x
 a (complete replacement) tint

does work though, and replaces the single node with a triangle, where all match and replacement nodes are closed.

Conclusion: A match graph can consist of entirely closed nodes if it matches the entire connected internal graph.

Preserving open node identity is easy, you simply choose to reuse a label, the arcs have already been deleted so degree matching is not needed. Closed node matching to the internal graph is harder because degree does need to match, but then for any combinatorially generated rule, there will be some internal state that could match it.

Using the python interpreter I have managed to create two disconnected internal graphs, but that looks like an interpreter bug where the second line triggers twice:

thequickbrownfoxjumpsoverthelazydog (START ) plorpasmita
plorp ( -- replace 4 nodes with triangle and tail -- ) panga

In the Haskell interpreter, the second line only triggers once. I think the spec prevents the internal graph from becoming disconnected.

Argument for the Eodermdrome command superset calculation:

1) A full graph replacement will accept any sequence of lowercase characters, in any order, with any number of duplicates, and whether the nodes are open or closed is irrelevant.

2) There are sum(A001349₁, ..., A001349₂₆) unique graphs that could be represented on the replacement side.

3) On the match side, there are also sum(A001349₁, ..., A001349₂₆) unique graphs that could be represented by unique combinations of up to 26 lowercase letters. They will all be valid complete internal state graphs obtainable from 2.

4) Some of those match graphs will also be valid-sub graphs, but that doesn't add or subtract from the total in 3

5) because of 1, all permutations of 2 and 3 are valid match and replacements, that could be triggered from at least one achievable complete state graph (and possibly from sub-graph matches).Salpynx (talk) 09:57, 2 February 2019 (UTC)

I'm not sure we are talking about the same thing. What I was trying to point out is that two commands without I/O can have their match and replacement subgraphs be identical as unlabeled graphs respecively, but still be non-equivalent because of the added requirements for handling open and closed nodes. This means that your formula underestimates the maximal number of possible commands. --Ørjan (talk) 00:10, 3 February 2019 (UTC)

Thank you for clarifying! I understand what you are saying now. I have created some 4 node only examples that prove what you say is correct. Different replacements with the same unlabled form have potentially different and significant effects on the resulting state graph. The internal state graph needs to be asymmetrical for this to be noticable, I started with (unintentionally) symmetrical graphs and managed to convince myself too quiclky that unlabled graphs ended up being sufficient/equivalent for replacements because the labels do not persist between commands. Oops. I'll go back to the drawing board. Now that I'm aware of it I'll hopefully be able to use this for some effect -- depending on the initial state, sometimes all labelled graph replacements end up being equivalent, other times they are very different as you point out. Thanks for setting me straight! Salpynx (talk) 05:31, 6 February 2019 (UTC)