Talk:Norfuck

I would really like some feedback from those who are experts in these sorts of languages. Is my language really Turing complete, or am I missing something here? --Ostracod 15:36, 3 October 2009 (UTC)

It's obviously Turing-incomplete. First of all, it's obvious that a program consisting of nothing but > cannot possibly have TC behaviour by itself (a program can be TC by itself without input, but this requires it to exhibit behaviour like, for instance, running all possible BF programs in parallel; the (equivalent) programs that are nothing but >s clearly have degenerate behaviour). Therefore, I'll consider only programs that contain at least one ! or <. Both those commands reset the memory head to the start of the tape; thus, any such program has the memory head reset to the start of the tape every cycle. No command can move the memory head to the left of where it starts; and the only command that moves the memory head to the right is >, which moves it 1 square per > command. Therefore, the memory head location cannot get further from the start of the tape than the number of >s in the program, i.e. it moves over only a finite area. Each tape element stores a finite amount of data; the state also stores a finite amount of data, so there's only a finite amount of data stored by the program altogether at any one time, and this amount can never increase. A language which only has finite data storage, whose account can never increase, cannot be TC (this is one of the most common ways to prove a language non-TC); in fact, Norfuck is a finite state automaton.

The rule 110 'proof' fails because rule 110 is only TC if given an infinitely long tape, with a periodic pattern on it to begin with. Norfuck has no method of simulating this; it can simulate subsets of rule 110 programs, but unfortunately no TC ones. --ais523 20:25, 3 October 2009 (UTC)

(to Ostracod) I don't think your proof works as given, anyhow. First, to make it Turing complete you need to be able to use unbounded memory, which doesn't work if you really need to write code for each CA cell separately. Secondly, rule 110 itself is problematic in that its proof for Turing completeness requires the initial cell setup to be infinite, in a complicated (but repeating) pattern. There are other less simple cellular automata without that second problem, though. For one thing, any Turing machine can be thought of as a cellular automaton where there just happens to be one special cell known as the tape head. You still definitely need some way to handle unbounded memory, though.

Another thing, I think your description has a bug, I think one of your > definitions should be for !. --Ørjan 20:38, 3 October 2009 (UTC)

I fixed that one already, in the way that makes the example programs correct. --ais523 20:41, 3 October 2009 (UTC)

Awww drat, I was really hoping it'd be Turing complete! At least a language can still be "interesting" if it isn't Turing complete. I've been wondering for a while whether the language needed to cope with limitless memory to be TC. Well, now that I know, I'll fix any claims about Turing completeness. Thanks for the help. --Ostracod 01:45, 4 October 2009 (UTC)