Talk:Thue (programming language)

From Wikipedia, the free encyclopedia

This article was nominated for deletion on 28 Sept 2006. The result of the discussion was no consensus.

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.