Talk:Befunge/index.php

I'm actually curious as to whether this is TC. It certainly has programs that run programs on a universal Turing machine, and it certainly has a program that run an arbitrary program input by a user on a universal Turing machine. But does it have a single program for every Turing machine? What about ones with rules tables too big to fit into 80x24? It's borderline, I think. —ehird 16:00, 5 November 2010 (UTC)

Well, actually, it can't run an arbitrary user-inputted program; only one that'll fit into Befunge-93's limited memory. —ehird 03:32, 7 November 2010 (UTC)

Proof that the language is Turing-complete: you can trivially write a BF interpreter in it, by reading strings from user input onto the stack (easy in Befunge-93), then running them.

Proof that the language is not Turing-complete: it's impossible to compile all Turing machines into it, because there are an infinite number of Turing machines yet a finite number of Befunge/index.php programs.

Confused yet? --ais523 03:37, 7 November 2010 (UTC)

So this is a different kind of problem. I assume you have infinite stack size, and infinite brainfuck memory? If so then it is Turing-complete with specially formatted input, I think, does that count? Turing-completeness does not normally deal with input/output? --Zzo38 18:49, 7 November 2010 (UTC)

Interesting, this one. If it has to work without input, so that the brainfuck program-to-run is created within the 80x24 field, then it doesn't have the ability to run all the arbitrary brainfuck programs exceeding the field's limits. However -- you can write a brainfuck-in-brainfuck interpreter in less than 80*24=1920 characters. So, you could make a Befunge/index.php program that pushed a fully functional brainfuck interpreter in the stack, and then executed it with X. But still the question is about input, I guess -- this brainfuck-in-brainfuck interpreter could not have the arbitrary brainfuck programs to run without there being the possibility for input (ie, the brainfuck-in-brainfuck program using brainfuck's own "," instruction to load the brainfuck program to interpret, instead of having it encoded in it). But then the question would be about X-brainfuck-interpreter-instruction's I/O capability, and not anymore about Befunge/index.php's Befunge-based I/O... ;) --Keymaker 14:39, 8 November 2010 (UTC)

Why can't it run an arbitrary user-inputted program? No limit is put on the size of the stack in Befunge-93.

In spring of this year on the IRC channel I proposed a language called ℒ. ℒ is a severely restricted subset of your favourite indisputably Turing-complete language (say, Pascal) -- so severely restricted, in fact, that you can only write a single program in ℒ. But that program is a Universal Turing Machine simulator. Is ℒ Turing-complete?

There were two opinions on this question that echo the two answers ais523 gave above: 1) Yes, because every Turing Machine maps to (some ℒ program, some input); 2) No, because not every Turing Machine maps to some ℒ program.

From this I put "Whether input is involved or not" on my list of "issues that would need to be resolved in order for people to agree on what Turing-complete meant" and after contemplating the matter in the intervening months I came to consider that Turing devised his machine in the era before computers were expected to store programs (natch) so he included the tape in his definition of the model, and this makes Turing machines models of computations, while the bulk of the study of computability has been on functions which correspond to Turing machines without tapes and blah blah blah this is boring shut up Chris. --Chris Pressey 03:57, 17 November 2010 (UTC)

I don't think that implementing brainfuck means that a language is TC, because you can simply create a langauge that has only one valid program which is a brainfuck interpreter. Secondly, there are a finite number of programs in this esolang, and there are an infnite number of brainfuck programs, so there must be a program that can be written in brainfuck but not in this esolang, and therefore it is probably not TC. --None1 (talk) 10:24, 30 August 2023 (UTC)