Talk:Thue

From Esolang
Jump to navigation Jump to search

How exactly is Thue self-modifying? It can't change it's own rewriting rules. --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. --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". --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)? --Safalra 10:48, 23 Oct 2005 (GMT)
I'm pretty sure Thue (the name) is /tʉɛ/ using IPA. --BodyTag 11:47, 23 Oct 2005 (GMT)
Ah, thanks. Now I see how ɛ could be transcribed as 'eh' - the slang word 'meh' is pronounced /mɛ/. --Safalra 20:09, 23 Oct 2005 (GMT)
But it still seems more natural to transcribe /ɛ/ as 'e' - 'eh' to me would suggest an elongated version, more like how I've heard "meh" pronounced. -- 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". --Rune 16:03, 23 Oct 2005 (GMT)
Your explanation makes perfect sense to this American English speaker. --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... --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". :-) 71.255.111.251 21:28, 9 March 2008 (UTC)

Thue and Markov algorithms

Isn't Thue equivalent 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. --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::=<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. --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. 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;
		}

--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?) 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. 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? 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.
--Ørjan (talk) 02:22, 7 September 2013 (UTC)

Linear Feedback Shift Register

For the code used 'to demonstrate Thue's nondeterminism'
Looks to me like it's simulating a LFSR
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 is, in fact, a correct Markov algorithm, but not a Thue program.

Here is a program that does this task correctly:

https://github.com/yoelmatveyev/marthue/blob/master/examples/thue/roman.t

This example on Github produces the Roman numeral MDCCIII. The input must be written with delimiters as "|>***|". The repository contains a second version, written in a very different style, which also requires delimiters "|******|", as well as a version that outputs the number as a string.

Retrieved from "https://esolangs.org/w/index.php?title=Talk:Thue&oldid=73289"