Talk:TLWNN
TLWNN is turing complete (untested)
by isomorphism with Brainfuck without I/O and with a tape with 5 nonnegetive unbounded cells:
At start must be: [@]>&**** + converted to !&![>@<]>& - converted to !&!<@& (- make an Undefined behavior when the cell is 0) > converted to >\>\>\>\<<<< < converted to >>>>\<\<\<\< [ code ] converted to [>>>>>@<<<<<][ code >>>>>*\<\<\<\<\[>>>>>@<<<<<]>\<\<*>>\>\<<<!&!<&@!!]*>>\>\>\>\>\>\<<<<<\<\<*>>\>\<<<!&!<&@!!
How it works:
Every cell presented by a packed stack which has contained (before the packing) a [@] at the bottom, then some [>@<] (The value of the cell is the number of [>@<]). The cells are on the 5 toppest places of the main stack. Then there are some loop calls (used for recorsion, and thats is for looping).
To unpacking a stack correctly (that the result will be like the stack before packing) the code !&! is used.
to increment a register, it is unpacked (with !&! ) to the auxiliary stack, a [>@<] is pushed to there, then it packed back. The decrement is smiliar.
The left and right translations worked by rotating a cycle of 5 places (of the cells) on the main stack.
The loop is the hard part: In short, it saves a copy of itself under the cells, and when the cell is nonzero, the copy is duplicated and one of the copies is executed, and when the cell is zero, the copies are deleted.
- A few initial observations:
- The initialisation can be written in less code:
[@]>&****. - You seem to be missing a
>in the translation of BF<. - This seems to be essentially a simulation of a Minsky machine.
- What is the loop code meant to be?
?is not a TLWNN operator. Besides, ISTM it ought to be possible to write the loop code such that the loop body only occurs once.
- The initialisation can be written in less code:
- But I'll have to study it more when I've time. -- Smjg 01:11, 2 June 2009 (UTC)
- Changed.
- Fixed
- Its the same principle, but in all version of Minsky Machine I know, the control structures are based on "goto"s but not "while"s
- Fixed. I used
?as a macro for the translation, and I forgot to replace it with its TLWNN's code. - I hope that has no errors.--(this comment by 77.126.179.189 at 13:03, 4 June 2009 UTC; please sign your comments with ~~~~)
- Thinking about it now, I suppose this machine is to the Minsky machine as 1-bit BF is to the Turing machine. As such, I believe it should be Turing complete, but it would be nice to come up with an actual proof. -- Smjg 15:23, 11 August 2009 (UTC)
- I've just discovered the name for BF with a fixed number of unbounded cells: Universal Register Machine. This should probably have an article here. But that piece states that URM is Turing complete – something that's shown further by the Fractran → Collatz function → 3-cell URM mapping. So I suppose we can conclude that TLWNN is TC after all. — Smjg (talk) 22:21, 15 March 2012 (UTC)
- I disagree that fixed-cell BF = URM; how do you translate the fixed-cell BF loop
[>]into URM form? —ehird 22:25, 15 March 2012 (UTC)
- I disagree that fixed-cell BF = URM; how do you translate the fixed-cell BF loop
- OK, so there's a difference there. But I've done a bit of analysis on the Haskell code on Collatz function. All of the
<and>symbols within each loop balance each other out, and so each instruction is always executed with the memory pointer in the same position. So that code could just as well be written to generate URM code, thereby proving 3-cell URM to be Turing complete. — Smjg (talk) 12:30, 16 March 2012 (UTC)
- OK, so there's a difference there. But I've done a bit of analysis on the Haskell code on Collatz function. All of the
- Indeed, Ørjan couldn't find any use for unbalanced loops with so few cells, so the distinction is probably purely academic. —ehird 20:07, 16 March 2012 (UTC)
Example
The infinity loop +[+] is translated to:
[@]>&**** !&![>@<]>& [>>>>>@<<<<<][ !&![>@<]>& >>>>>*\<\<\<\<\[>>>>>@<<<<<]>\<\<*>>\>\<<<!&!<&@!!]*>>\>\>\>\>\>\<<<<<\<\<*>>\>\<<<!&!<&@!!
--87.68.248.230 12:40, 22 May 2009 (UTC)
- I discovered earlier that the implementation of the loop was incorrect (Instead of regular while loop, it was like while but without checking in the second iteration). Now it fixed. --77.125.146.64 16:31, 25 May 2009 (UTC)
Title display
I (or another administrator) could simply hide the title in the CSS, as is done to the main page, if you want something that avoids the ugly horizontal rule. But I'm a bit uneasy about hiding or changing the title of articles in general, since one of the principles of a wiki is that you can link to an article with its title. —ehird 13:04, 28 March 2012 (UTC)