Talk:Cythan

I don't think this is Turing complete

Let M be either the index of the last cell with a nonzero value, or the largest value in a cell, whichever is larger. I don't think there's any way for a program to increase the value of M without trivially entering an infinite loop (by sending the instruction pointer off to infinity). But there's only a finite number of configurations for any given M. As such, I think this is actually a finite state machine.

For the language to actually be Turing complete, you'd need some way to create larger numbers. --ais523 06:44, 25 May 2021 (UTC)

Actually, I'm pretty sure it is indeed Turing Complete, by the only fact that we are able to program increment, if_0, loop, and by combinaison addition, multiplication, shift etc.. in the new compiler we are making. The link to the Compiler.

I don't see how for a language to be Turing Complete it need to be able to make arbitrary large numbers. A computer, for exemple, store everything in bytes. And to make arbitrary large number, you could use multiples of them. You can do the same in Cythan. Cypooos (talk) 19:31, 30 August 2021 (UTC)

As far as I can see, ais523 is right. Bounded-storage machine is a useful concept to capture the difference between something that is programmable (as Cythan is) but lacks unbounded storage, Turing machines, and finite automata specified by states and transitions. (Aside: The language is *very* close to actually being TC. For example, filling up the memory with the repeating pattern 0 1 2 would push it over the threshold... the idea being that code[0]+=2 can then be used to increment a counter (for that to work for a value n, we need to execute an instruction at address n that copies code[0] to some code[x]; the 0 1 2 pattern allows us to jump back to where we came from if we store the desired return address in both code[1] and code[2]...)) --Int-e (talk) 21:52, 30 August 2021 (UTC)

I know it's been two years, but I have some new informations.

First, I agree, with a finite-length program, it isn't turing complete. I kinda didn't know what really was a Turing Complete program. But as Int-e hinted, there is multiple way to make it Turing Complete with a infinite default pattern in it.

One way to prove it would be to replicate a Turing Complete cellular automaton. And you can make Rule 110 in it, but with some modifications so that it is working on a Cythan machine.

The idea is to cut the band of the Cythan machine in a serie of blocks repeating. Each block will have the code to look for a specific pattern on his left, his, and his right blocks, change his value, and then call the next one. So that it does restart and iterate, we need to test if a bit that isn't set by default is or not set. If it is, then we call the next block, if it isn't, we set it and restart to block 0. That way at iteration N we calculate the first N blocks. Off course, we can initialized the program to represent a certain starting position.

Also, since Rule 110 is on a infinite (both way) band, we can have the even blocks represent the right side of Rule 110 band and the left side of Rule 110 band as the odd numbered blocks. That way a block numbered i really look at block's i-2, i and i+2 to know what value to set.

Also the proof that it isn't turing complete becaus eyou can't make arbitrary large number isn't valid. First, because you could technically have store every positive integer in the Cythan machine band at the beginning, and second because it doesn't prove anything. If you can make arbitrary size tables but not integer for example, it could very well be turing complete by representing every integer as his base-2 notation in a table.

I know this proof is missing some keys arguments and isn't concise enough. I'll make a well written one, with diagrams, maybe publish it, and link it as soon as it's done.

--Cypooos (talk) 16:23, 25 July 2023 (UTC)