Talk:Chaingate

I don't understand your argument "the ability to make finitely many irreversible changes that some fs have doesn't change the computational class of the language because you could just start executing after those have happened, and thus the lack of such changes in Free Chaingate doesn't matter". It seems to me that it could very well be undecidable whether two values will ever converge to the same path, even if f is computable. E.g. this is probably not even proved to be checkable for the usual Collatz function. --Ørjan (talk) 00:47, 4 March 2017 (UTC)

I was trying to express the fact that I was only concentrating on cases where the ultimate fate of iterated f was decidable, but I agree I didn't express that very well. --ais523 20:47, 4 March 2017 (UTC)

I share Ørjan's confusion. In fact I have trouble seeing in what sense Free and Freeer Chaingate can be TC, since from any known state one can compute all future states (which, as the article points out, are part of a tight loop), so one can also check any alternative decidable acceptance condition for those states. So to make it TC, you need to have an undecidable acceptance condition? (This doesn't necessarily mean that these languages are boring; they may still be powerful enough for encoding LBAs, and exhibit interesting behavior similar to Malbolge (which is really a huge finite state machine)) Int-e (talk) 12:06, 26 January 2019 (UTC)

You can implement The Amnesiac From Minsk level 4 in Chaingate pretty directly. Of course, you could argue that that can't be TC on similar grounds.

This all comes down to what sort of "halt conditions" you allow, in languages which can't halt naturally. I'm assuming that a TCness proof would involve compiling some other language into Free Chaingate, at which point you could detect a tight loop in that language and talk about what the Chaingate equivalent of it was. The idea behind Freer Chaingate is that you might be able to send control flow past the irreversible transition when that happened, leading to a less controversial definition of Turing-completeness, but after thinking about it, it might well be that a TCness construction for Chaingate doesn't allow commands to run conditionally in that sense. --ais523 23:26, 26 January 2019 (UTC)

Never mind. I managed to miss the "or infinity" in the description of the modulus n, somehow. Sorry. Int-e (talk) 00:05, 27 January 2019 (UTC)

Note that for any Turing Machine M with states S and alphabet Σ, one can define a corresponding Chaingate-M language that is equivalent to M, by taking A to be the set of configurations of M (A = S×Σ^*×Σ^*), and f as the corresponding transition function. The Chaingate-M program corresponding to a configuration c is the singleton list [c]. In particular, for any universal TM U, Chaingate-U is TC. Of course this is unsatisfactory in that the function f is the sole source of TC-ness. Int-e (talk) 12:06, 26 January 2019 (UTC)