Examine individual changes

'How exactly is Thue self-modifying? It can't change it's own rewriting rules. --[[User:Chris Pressey|Chris Pressey]] 23:07, 5 Jun 2005 (GMT) :OK. I'm not really familiar with Thue. I just saw that it replaces it's own rules, and thought of that as self-modification. I'll remove the category. --[[User:Rune|Rune]] 23:17, 5 Jun 2005 (GMT) ==Pronunciation== Regarding pronounciation: If it is correct that it is named after a norwegian, I (as a norwegian myself) find the "TOO-ay" pronounciation strange. Normal norwegian pronouciation of Thue is more like "TOO-eh" or "TOO". --[[User:Rune|Rune]] 23:17, 5 Jun 2005 (GMT) :What's the difference between "TOO-ay" and "TOO-eh"? With British pronunciation they'd be the same - much as we pronounce 'hay' and 'heh' (and also 'hey') identically. Is 'eh' meant to represent a shorter sound (like an aspirated schwa)? --[[User:Safalra|Safalra]] 10:48, 23 Oct 2005 (GMT) ::I'm pretty sure Thue (the name) is /t&#649;&#603;/ using IPA. --[[User:BodyTag|BodyTag]] 11:47, 23 Oct 2005 (GMT) :::Ah, thanks. Now I see how &#603; could be transcribed as 'eh' - the slang word 'meh' is pronounced /m&#603;/. --[[User:Safalra|Safalra]] 20:09, 23 Oct 2005 (GMT) :::: But it still seems more natural to transcribe /&#603;/ as 'e' - 'eh' to me would suggest an elongated version, more like how ''I've'' heard "meh" pronounced. -- [[User:Smjg|Smjg]] 18:00, 16 March 2008 (UTC) ::You pronounce 'hay', 'hey' and 'heh' indentically? Didn't know that. I guess 'TOO-eh' is not a good way to describe it then. I guess the "-eh" would be approximately the way you pronounce the vowel in "when". --[[User:Rune|Rune]] 16:03, 23 Oct 2005 (GMT) :::Your explanation makes perfect sense to this American English speaker. --[[User:Graue|Graue]] 16:55, 23 Oct 2005 (GMT) :Hmm... well, I wouldn't ever doubt a native speaker about pronounciation. But I would also interpret the wording in the language description as making it explicit that the name of the ''language'' is to be pronounced "TOO-ay". Which may be strange and inconsistent, but hey, this is esoteric programming; it certainly wouldn't be the first time... --[[User:Chris Pressey|Chris Pressey]] 15:17, 8 Jun 2005 (GMT) :Funny - when I was reading this, I thought that the best way to describe the pronunciation would be "as if one were in the process of spitting, loudly". :-) [[User:71.255.111.251|71.255.111.251]] 21:28, 9 March 2008 (UTC) == Thue and Markov algorithms == Isn't Thue equivalent [http://en.wikipedia.org/wiki/Markov_algorithm Markov algorithms], if we ignore I/O and remove the non-determinism by insisting that only one rule applies at any one time? In which case, this seems a simpler way of proving Turing-completeness that the arguement in the article. --[[User:Safalra|Safalra]] 19:02, 22 Oct 2005 (GMT) :Hmmm, but how can one just remove the non-determinism from Thue? It's an important part of the language. I don't know about these proving things, but you could at least emulate the Turing-complete Markov algorithms in Thue and prove Thue Turing-complete that way (although it's not gonna be easy). --[[User:Keymaker]] ::Have some kind of marker that moves through the program from the left. When one of the Markov rules applies, it turns into another marker that moves back to the beginning, otherwise it carries on. Note that this will result in a huge number of rules, as the rules for 'carrying on' mustn't apply when one of the Markov rules applies. Imagine a Markov algorithm with just one rule: A -> B ::This could be translated into Thue in the following way: >A::=&lt;B >B::=B> >C::=C> >D::=D> and so on |<::=|> B<::=<B C<::=<C D<::=<D and so on ::= |>string to which to apply Markov algorithm ::Here > is a rightwards-heading marker and < is the leftwards heading marker. The two cases of 'and so on' should be replaced with extra rules for all the other characters. This becomes much more complicated as the Markov algorithm becomes more complicated, but as far as I can see it generalises perfectly. --[[User:Safalra|Safalra]] 13:30, 23 Oct 2005 (GMT) :Thue seems identical to Lindenmayer Systems (L-Systems) to me. I've looked over all three - semi-thue, markov, and L. L-Systems allow for stochastic (non-deterministic) replacement using multiple right-hand side rules. [[User:Wildhalcyon|Wildhalcyon]] 18:06, 10 Jun 2006 (UTC) ==Bug in C Implementations== At least two of the C implementations that are linked on the main page have this bug: /* Sort the LHS list - Just a bubble sort */ for (i=1;i<j;i++) for (k=0;k<i;k++) if (target[i] < target[k]) { c = target[i]; temp = rnum[i]; target[i] = target[k]; rnum[i] = rnum[k]; target[k] = target[i]; rnum[k] = temp; } The code should read: /* Sort the LHS list - Just a bubble sort */ for (i=1;i<j;i++) for (k=0;k<i;k++) if (target[i] < target[k]) { c = target[i]; temp = rnum[i]; target[i] = target[k]; rnum[i] = rnum[k]; target[k] = c; rnum[k] = temp; } --[[User:Nthern|Nthern]] 00:54, 16 July 2010 (UTC) ==Empty original string, non-empty replacement string== It may be worth noting that, while the spec, and this article, say that the list of productions is terminated by line which consists of only a "::=" (optionally surrounded by whitespace), both John Colagioia's original implementation, and Frédéric van der Plancke's implementation in Python, terminate the list of productions on any line in which only whitespace precedes the "::=", even if there is a non-whitespace replacement string after the "::=". From an implementation standpoint, that seems somewhat reasonable, but if we go strictly by the spec, then we may ask, what is the meaning of, say, "::=g" -- insert a "g" into a random point in the string? (Are there any implementations which make this interpretation?) [[User:Chris Pressey|Chris Pressey]] ([[User talk:Chris Pressey|talk]]) 01:25, 11 September 2012 (UTC) :Correction: FvdP's implementation considers "::=g" and the like to be a "Malformed production" and throws an exception. [[User:Chris Pressey|Chris Pressey]] ([[User talk:Chris Pressey|talk]]) 02:44, 11 September 2012 (UTC) == Challenging Problem == I've been messing around with Thue and written several interesting (to me) programs, such as a unary to binary converter or a binary to decimal converter. Now I'm wondering if anyone can figure out how to solve this one. The issue is to (given a predefined alphabet of symbols for the input string) find and mark the end and beginning of an input string without modifying the contents of the string (in the end). Since Thue is Turing complete, this ''is'' possible, but how? It is much easier if you have one end marked already by a non-alphabet character, or even have a non-alpha character anywhere in the string. For instance, with an alphabet of (0,1), this program will mark the beginning with . and the end with ,: ,1::=.>####1> ,0::=.>####0> >1::=1> >0::=0> >#::=> >>::=, 1.::=1 0.::=0 ::= ,1101101 But how to do it without any non-alpha characters '''and''' keeping the string the same? [[User:Numeri|Numeri]] ([[User talk:Numeri|talk]]) 22:51, 6 September 2013 (UTC) :This is impossible, and here is an argument why: :*The program has to halt on your final string, therefore no rule can match it. :*The initial string is not the same as the final string, therefore some rule must match the initial string to even get started. :*The initial string is a subset of the final string, and rules cannot detect string ends, therefore every rule matching the initial string must also match the final string. :*So the final string must match both no rules and some rule. Contradiction! :More generally, a thing to remember about Turing completeness is that it really says that you can ''encode'' any computation in your language, but it says nothing about preserving the ''original'' encoding of input, output or data when doing so. Input and/or initial data may need to be arbitrarily encoded as part of the initial setup, and output and/or final data may need to be decoded after the program ends. Not all Turing complete formalisms even have a distinction between input, initial data, or program! [[Lambda calculus]] is a prime example. :--[[User:Oerjan|Ørjan]] ([[User talk:Oerjan|talk]]) 02:22, 7 September 2013 (UTC) == Linear Feedback Shift Register == For the code used 'to demonstrate Thue's nondeterminism'<br> Looks to me like it's simulating a LFSR<br> [[User:DMC]] 13 April 2018 == Converting to Roman numerals == The program that is supposed to converts a group of * to Roman numerals does not work because of the non-deterministic choice of the rules, i.e. ****** may be interpreted as either VI, IVII, IIVI or wrongly as IV, while ********** (10 stars) may be evaluated into X, IIX, IXIII, IIIXI, IXI, IVX, IVIIVI, IIIVII, IVIIIV... or wrongly as XII. It seems that the author of this code had Markov-like strictly sequential algorithm in mind.'