Talk:I/D machine

Some notes

First of all, congratulations on inventing this thing. The simplicity is incredible. I can't believe it's real.

Whereas I don't doubt you have everything under control regarding the cyclic tag translation, I'm writing these notes here for the benefit of everyone; I was surprised by the simplicity of this method when I devised it for my cyclic tag language to Kantate translation back in the day.

It's fascinating how well cyclic tag language works with array/random-access memory. The target language more or less only needs a method for increasing cells. It amazes me how simple, blind increasing of cells will create the conditional behaviour of the '0' and '1' instructions. The memory string can be implemented with two pointers: one that points at the beginning of the simulated memory string's first digit and one that points at its last digit. Assumed is an array that is unbounded and empty/filled with zeroes. In the simulated memory string, 0 is represented with 0, and 1 with what I call 'the fixed amount'. In this case perhaps the fixed amount of 1 suffices, in my Kantate work it had to be something else because the Kantate instructions had to be interleaved with the simulated memory string. Here's a way of translating the cyclic tag language instructions:

• ';' becomes simply a matter of increasing the start pointer by the fixed amount. As the starting pointer moves, the erasing of first digit is simulated.
• '0' becomes adding the value of the cell the start pointer points at (either '0' or 'the fixed amount') to the end pointer (thus causing it to point to the next simulated cell, or not). If first in memory string was 0, the end pointer didn't move (p+0=p). If first in memory string is 1 (the fixed amount), the end pointer now points to the next cell (which has value 0, since the array is filled with zeroes) -- the appending of a 0 has been simulated.
• '1' becomes adding the value of the cell the start pointer points at to the end pointer (like above), then adding the value of the cell the start pointer points at to the cell the end pointer (which was just updated) points at. If first in memory string was 0, the end pointer didn't move -- and since that first was 0, adding it the last cell won't change the last cell's value (whether it's 0 or 1/the fixed amount). If first in memory was 1 (the fixed amount), the end pointer moved one cell forward (and the cell it now points at is 0), and when the value under the start pointer (1 in this case) is added to that 0-cell, the cell becomes 1 (the fixed amount), and the appending of a 1 has been simulated.

--Keymaker (talk) 11:13, 17 March 2018 (UTC)

That's a pretty elegant construction! I don't think the way it does conditionals works for the I/D machine in particular because "add A to B" is actually very hard to do in the I/D machine (unless A is a constant, when it's trivial), so I used the "bit bucket" approach instead (basically, having a duplicate queue that unwanted elements get pushed on). Note that for every I command in the source, something has to get incremented, so you'd need somewhere to throw away unwanted increments anyway, and a spare queue is a good use of that. --ais523 05:57, 18 March 2018 (UTC)

how to convert between the different command views?

for ex: how to convert the program III into the 1-command view? --Pro465 (talk) 09:35, 28 May 2023 (UTC)

Just use run-length encoding: count the number of I before the first D and between each D, and write down the resulting list of numbers. (If there are two D in a row, there are no I between them so you have to write a 0.) This only works for programs that end with D, but that isn't a restriction that hurts the language's Turing-completeness. --ais523 12:48, 30 May 2023 (UTC)

so, they are not really equivalent in the sense of "isomorphism that preserves semantics exists between them", but in the sense of "they are equivalent in most common cases, and the cases where they are not, don't affect their turing completeness"? --Pro465 (talk) 09:19, 31 May 2023 (UTC)

Here's an alternative way to think about it / perform the translation: D is equivalent to 0, and I n is equivalent to n+1. So you can change all the D to 0, then merge all the I into the numbers that follow them. (Again, if the program doesn't end with a D, you won't be able to entirely convert it to numbers: that's why some of the fragments in the Turing-completeness proof end with III, which will end up adding 3 to the first number of the next fragment when the fragments get merged into a single program). --ais523 12:51, 30 May 2023 (UTC)

why is this a computational model?

And could you say if I can add Xeroxer to the category? Thanks! --Pro465 (talk) 15:00, 18 June 2023 (UTC)

I cant see why this is turing complete

Listen to me: I increments the current cell by 1. Ok, How do you subtract? D only does d=*d. If you say integer overflow then *d is limited and therefore it has limited memory and is NOT turing complete. I can name a program that I/D machine cant do: *d=*d-1. --Yetyetty1234567890 6:13, 12 July 2023 (UTC)

you don't need subtraction to be turing complete. you only need to simulate everything a turing machine can do, not literally do it.

think of it this way: even though a minsky machine with jump if equal and increment instructions cannot actually decrement a register, it can simulate that by incrementing everything else, (altho it needs an additional register to simulate 0). --Pro465 (talk) 07:31, 15 July 2023 (UTC)

A language $L$ that has no I/O actions is said to be Turing-complete iff there exists a computable function $f$ such that for any Turing machine $M$, the program $f(M)\in L$ halts iff $M$ halts. --Hakerh400 (talk) 09:22, 15 July 2023 (UTC)

Pro465, Then how do you simulate *d=*d-1? --Yetyetty1234567890 13:47, 15 July 2023

Yetyetty1234567890, note that Pro465's description is imprecise. Please read the precise definition I wrote above. If a language doesn't have I/O actions, then all you can ask is whether a given program halts. What the program does with its internal memory doesn't affect Turing-completeness. To elaborate more on the definition I gave: a language $L$ without I/O actions is said to be Turing-complete iff there exist computable functions $f:T\mapsto L$ (where $T$ is the set of all Turing machines) and $h:L\times \mathbb {N} \mapsto \{0,1\}$ that follows the semantics of $L$ such that any given Turing machine $M$ halts iff there exists $n\in \mathbb {N}$ such that $h(f(M),n)=1$. The answer to your question is that, even though you can't decrement a value, I/D machine is still Turing-complete because it complies with the definition of Turing-completeness for languages without I/O actions. --Hakerh400 (talk) 14:21, 15 July 2023 (UTC)

I may be wrong here, but how do you input a natural number to a language with no IO? I think you meant for $f$ to have the type $T\times \mathbb {N} \mapsto L$ instead. --Pro465 (talk) 14:38, 15 July 2023 (UTC)

I'm not sure what part you don't understand. We don't input a natural number to a language, we input it to a function. Consider this slighlty different definition: a language $L$ without I/O actions is an ordered pair $(P,g)$ where $P$ is the set of all syntactically valid programs in $L$ and $g:P\times \mathbb {N} \mapsto S$ (where $S$ is the set of all program states) is a computable function that takes a program and a natural number $n$ and returns the state of the program after simulating it for $n$ steps. Language $L=(P,g)$ is Turing-complete iff there exists a computable function $f:T\mapsto P$ (where $T$ is the set of all Turing machines) and a set $h\subseteq S$ such that any Turing machine $M$ halts iff there exists $n\in \mathbb {N}$ such that $g(f(M),n)\in h$. I think we can't get more precise than this. --Hakerh400 (talk) 15:42, 15 July 2023 (UTC)

Brainfuck minus - also can't decrement cells – it can't ever set them back to 0 after they become nonzero, just like the I/D machine can't. Yet, it's Turing-complete too. There's no requirement that a Turing-complete language stores numbers in an obvious way – just that it has *some* way to store them. In the I/D machine, data is normally stored using a queue that moves gradually to the right over the course of program execution: new data are added at the rightmost end of the queue, and data are read from the leftmost end (and once data is read, that part of the tape is disregarded from that point onwards). You could create a number that can be incremented and decremented by storing it on the queue in unary. Queue-based languages generally work by repeatedly copying the data from the tail to the head of the queue, and while you're doing that, you can increment or decrement a unary number by varying the details of the copying loop (i.e. maybe you add an extra digit as you copy it, or don't copy the first digit). --ais523 18:16, 15 July 2023 (UTC) 18:16, 15 July 2023 (UTC)

But Brainfuck minus - has a way of copying cells, while I/D machine does not. If it can, prove it! --Yetyetty1234567890 23:49, 15 July 2023 (UTC)

Have you not read I/D machine Turing-completeness proof? All the detail is there. (The proof as written doesn't use a "copy a single element" operation – rather, it has a "conditional push" operation that pushes something if the head of the queue is 5, or nothing if the head of the queue is 1. If you imagine a queue made out of 15 and 51 pairs, then it's possible to use that operation to copy the elements; first, conditional-push 51, then conditional-push 15. This means that only finitely many cell values can be copied, but BF-- is no different.) --ais523 23:53, 15 July 2023 (UTC)

I have 1 more problem before i read. control flow. It would require infinite memory for a single

while()

[

if(x=0)

[

f(x)

]

]

, because first D will move to a value and apply that function, but then it's been used. so you can't use it anymore. so you can't do anything after that.

and still copying. ----Yetyetty1234567890 24:57, 16 July 2023 (UTC)

Control flow is indeed hard to simulate well – the I/D machine's control flow isn't very good, but it is enough. The basic principle is that by storing a number of a certain size (in unary), you arrange things so that when the unary number finally finishes being read, the position of the instruction pointer within the I/D machine program will be different. (The longer a unary number is, the longer it takes to read, so the further the instruction pointer moves through the program while reading it; and because the I/D machine's instruction pointer wraps, you can make it move to the left by moving it a long way to the right.) Your control-flow instructions therefore have to be built into the data you're operating on – you get a sort of "time-delayed goto" by creating data of a particular length, so that when the program finishes reading it, the instruction pointer will be in the appropriate position. It is hard to write directly in this style, which is why the proof translates from cyclic tag (which uses the same form of control flow). --ais523 01:15, 16 July 2023 (UTC)

sorry for being off-putting, but you should really learn some things about computability instead of making others do the work for you. skepticism and wanting help are good, but not so much if the proofs are freely accessible on the internet and you don't even look at them. --Pro465 (talk) 06:02, 16 July 2023 (UTC)