Talk:Thue (programming language)

Untitled

The last program does not look like it would produce the results that its introduction indicates. I assume it must be called with 'r' so that rules are evaluated right-to-left. Otherwise, the program terminates immediately and does not rewrite the input. When running with 'r', it would produce one rewrite from 'abc' to 'ac'. But, at that point, it would halt. So, either way, the intended result wouldn't be achieved.

Maybe this would be more effective (called with 'l'):

b::=~0
b::=~1
a::=ba   -- or quite possibly a::=ab (depending on which end of the string the pattern matcher starts)
::=
a

I could be wrong about this so if the original author is around or someone else can confirm, then the main page can be corrected. At the very least, a more detailed explanation of the 'nondeterminism' of Thue is called for, in my opinion. — Preceding unsigned comment added by Johanatan (talk • contribs) 15 June 2007

The example is correct as it is. The initial state 'abc' is transformed by either of the two first rules to 'ac' while sending either 0 or 1 to the output stream. Then 'ac' is replaced by 'abc' using the third rule, and everything repeats. Thomas Nygreen (talk) 16:06, 5 August 2011 (UTC)

The sample program to add one seems to have a bug in that it does not remove the leading underscore unless the sum is a power of two. It also has an ambiguous result in the case of the input of _01_, the choices being _01_, _01++, _10 and _01_, _1_, _1++, 10 --80.175.250.218 (talk) 10:40, 12 December 2008 (UTC)

I guess the creator did not care if the leading underscore was left there or not. To make the result completely predictable, just add an underscore to the last rule (i.e. _1++::=_10). Then the leading underscore will always be kept. Thomas Nygreen (talk) 16:06, 5 August 2011 (UTC)

It had several bugs, including a major one where _0_ could result in _1 or __ (this being completely incorrect). This was fixed by adding one simple statement, but it doesn't do anything for the leading underscore issues. The first issue is the non-deterministic removal of the leading underscore when there are leading zeros. The second issue is the removal of the leading underscore when there are no (more) leading zeros and a carry happens into the most significant digit, while the trailing underscore is always removed. It seems the easiest would be to always leave the leading underscore. Below is a program that would solve both always leaving the leading underscore, while also solving the _0_ case in a slightly different way Jordsan (talk) 19:42, 1 March 2020 (UTC):

1_::=1++
0_::=1

01++::=10
11++::=1++0

_00::=_0
_01::=_1
_1++::=_10

::=

_1111111111_

It seems removing the leading underscore is possible, but in no way as simple. Jordsan (talk) 19:42, 1 March 2020 (UTC)

Increment example output?

I don't see any output statements in the increment example, and unsurprisingly get no output when I run it in the reference implementation. Has anyone an idea how to make this example better in that respect? Marc W. Abel (talk) 01:50, 11 February 2013 (UTC)

The result is not sent to the output stream but kept in the program state Jordsan (talk) 19:42, 1 March 2020 (UTC)