Talk:Smurf

Has Smurf been proved Turing-complete?

Smurf is described on the Muriel page as an attempt to make a Turing tarpit from that language. Has a proof of Smurf's Turing-completeness actually been constructed? If not, I might work on it myself, as Smurf is a rather elegant language. --Safalra 18:31, 21 Oct 2005 (GMT)

Elegant indeed. Like the Lambdae, but with strings instead. --Ihope127 18:44, 21 Oct 2005 (GMT)

I have written an interpreter for a UTM in Smurf. It was easier than I was expecting:

"Written by 4D-enthusiast on 6/10/2012. simulates the 5-symbol 2-state turing machine described at http://mathworld.wolfram.com/UniversalTuringMachine.html"o
i"tape L"p
i"tape R"p
i"state"p
"\"tape L\"gh\"tape R\"g+\"tape R\"p\"tape L\"gt\"tape L\"p""L"p
"\"tape R\"gh\"tape L\"g+\"tape L\"p\"tape R\"gt\"tape R\"p""R"p
"\"1\"\"tape R\"g+\"tape R\"p""L"g+"\"D\"\"state\"p"+"0U"p
"\"0\"\"tape R\"g+\"tape R\"p""R"g+"\"D\"\"state\"p"+"1U"p
"\"4\"\"tape R\"g+\"tape R\"p""R"g+"\"U\"\"state\"p\"tape L\"g\"2\"+\"tape L\"p\"tape R\"g\"4\"+\"tape R\"p"+"2U"p
"\"4\"\"tape R\"g+\"tape R\"p""R"g+"\"U\"\"state\"p"+"3U"p
"\"3\"\"tape R\"g+\"tape R\"p""L"g+"\"U\"\"state\"p"+"4U"p
"\"2\"\"tape R\"g+\"tape R\"p""L"g+"\"D\"\"state\"p"+"0D"p
"\"0\"\"tape R\"g+\"tape R\"p""R"g+"\"D\"\"state\"p"+"1D"p
"\"0\"\"tape R\"g+\"tape R\"p""R"g+"\"U\"\"state\"p"+"2D"p
"\"4\"\"tape R\"g+\"tape R\"p""R"g+"\"U\"\"state\"p"+"3D"p
"\"1\"\"tape R\"g+\"tape R\"p""L"g+"\"U\"\"state\"p"+"4D"p
"tape R"gh"state"g+g"instruction"p

"\"q2\"p
\"tape L\"gq\"\\\"tape L\\\"p\"+
\"tape R\"gtq+\"\\\"tape R\\\"p\"+
\"0U\"gq+\"\\\"0U\\\"p\"+
\"1U\"gq+\"\\\"1U\\\"p\"+
\"2U\"gq+\"\\\"2U\\\"p\"+
\"3U\"gq+\"\\\"3U\\\"p\"+
\"4U\"gq+\"\\\"4U\\\"p\"+
\"0D\"gq+\"\\\"0D\\\"p\"+
\"1D\"gq+\"\\\"1D\\\"p\"+
\"2D\"gq+\"\\\"2D\\\"p\"+
\"3D\"gq+\"\\\"3D\\\"p\"+
\"4D\"gq+\"\\\"4D\\\"p\"+
\"instruction\"g+
\"\\\"tape R\\\"gh\\\"state\\\"g+g\\\"instruction\\\"p\"+\"q1\"p
\"tape L\"go\"\"o\"tape R\"go\"\"\"\"oo
\"q1\"g\"q2\"gq+\"q2\"g+x"

"q2"p

"tape L"gq"\"tape L\"p"+
"tape R"gtq+"\"tape R\"p"+
"0U"gq+"\"0U\"p"+
"1U"gq+"\"1U\"p"+
"2U"gq+"\"2U\"p"+
"3U"gq+"\"3U\"p"+
"4U"gq+"\"4U\"p"+
"0D"gq+"\"0D\"p"+
"1D"gq+"\"1D\"p"+
"2D"gq+"\"2D\"p"+
"3D"gq+"\"3D\"p"+
"4D"gq+"\"4D\"p"+
"instruction"g+
"\"tape R\"gh\"state\"g+g\"instruction\"p"+"q1"p
"tape L"go""o"tapeR"go""""oo
"q1"g"q2"gq+"q2"g+x

I have added new-lines for readability but they can just be removed. This will store the parts of the tape left and right of the head as separate strings, and output both of them every cycle. It automatically extends the tape when needed (and sometimes when not needed), so I'm pretty sure that this proves its Turing-completeness. Having written this, I actually really like Smurf now. It is a nice languuage, though awfully difficult to write anything that's got a complicated control flow.--4D enthusiast (talk) 11:41, 16 October 2012 (UTC)

Just as a warning, that particular Turing machine requires a tape that repeats infinitely in both directions in order to be Turing-complete (and the proof of its Turing-completeness in ANKOS is wrong). I think your construction generalizes to other Turing machines, though, so it should be good. --ais523 01:29, 28 April 2013 (UTC)

Year

In what year was this language created? --213.119.115.231 20:20, 21 Oct 2005 (GMT)

2001.. you can search for the announcement in this archive: http://esoteric.sange.fi/archive/2001-q2-1 Calamari 08:45, 19 Nov 2005 (GMT)

Smurf instruction minimalisation

If we limit the contents of Smurf strings to the same characters as the other instructions (which should have no effect on Turing-completeness) then it has three states (call them READING_INSTRUCTION, READING_STRING and READING_ESCAPED_CHARACTER) and 11 symbols ("\+pgiohtqx). This symbol set can be reduced further (without resorting to using multiple symbols to encode single instructions), although it may seriously reduce the elegance of the language:

1. Remove x, i and o - initialise the stack with the input (or the empty string if there is no input), and at the end of the program pop the string at the top of the stack (if there is one) and output it, and then pop another string from the top of the stack (if there is one) and execute it
2. Remove + and g, and create a new j command - pops two variable names from the top of the stack and joins their values, so + becomes "first"p"second"p"first""second"j and g becomes ""j (assuming the variable "" is unset)
3. Remove h and t, and create a new s command - splits a string into a head and a tail and pushes them onto the stack (tail first), so h becomes s"head"p"tail"p"""head"j and t becomes s"head"p

The reduces us to "\pjsq

The previous 'improvements' aren't too bad, but the one that follows is an ugly mess:

Also it might be possible to remove one state by changing the behaviour of " - instead of marking the beginning of a string, it marks one character to add to some 'string buffer', and the string is written when a character other than " is read (which is then ignored). This, though, is really inelegant, because of the use of a dummy instruction. If this paragraph wasn't clear, it means that something like:

"key""value"p

...becomes:

"k"e"y?"v"a"l"u"e?p

...where ? should be replaced by and symbol other than the quotation mark. Note that this removes the need for any escaped characters (and hence escape state), as something like:

"\\\""

...becomes:

"\""?

Note that there's no method for having newlines in a string now (as we can't add them into the source without introducing an extra symbol), but this doesn't affect Turing-completeness. Furthermore, constructing an empty string involves construction of a one-character string and then taking its tail - extremely inelegant. Obviously the behaviour of the q command would now change.

--Safalra 14:47, 22 Oct 2005 (GMT)

I have made something based on this instruction minimalization, it is called Smu. The quoting command is not supported in Smu, but preprocessor macros is support. Not counting preprocessor, there is 5 commands in Smu which is ()|=+ and input/output is done one bit at a time. --Zzo38 01:49, 14 January 2009 (UTC)

Hmm...you can also delete the \, since the " command does all the work. Please explain if that doesn't work.--User:A 11:09 20 Jul. 2018

Okay, if that is just unerrored, only 5 commands are needed.--User:A 11:33 21 Jul. 2018

Quine

Something interesting... with the online interpreter, I managed to make this quine:

"qoto"qoto"I was just talking and someone interrupted
Or was it a loud explosion?

Needless to say, it's rather abusive of the language. Its function, however, should be independent of the actual error message. (as long as there are no quotes in the error)

A worse abuse is:

It's hard to understand me from the language I use
There's no word in English for my style

Trivial perhaps, but I found them amusing. :P

-- Nonny

The empty string is also a quine. --Ihope127 15:39, 3 Dec 2005 (GMT)

Quines like the ones above are called "kimian quines" --Zzo38 20:43, 10 January 2009 (UTC)

Smurf seems very similar to underload. Challenger5 (talk) 04:47, 20 December 2016 (UTC)