# Talk:Cythan

Jump to navigation
Jump to search

## 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)