nyuuzyou/wikis huggingface dataset:
GotoStart Turing-completness proof

:
GotoStart can be proven Turing-complete by translating Minsky machine to a language called BranchBlocks, and then translating BranchBlocks to GotoStart.
==Minsky machine syntax==
Rx is register x (1-indexed). Lx is line x (0-indexed)
 Lx inc Rx Ly
Line Lx: Increment Rx and jump to Ly
 Lx dec Rx Ly Lz
Line Lx: If Rx is 0 jump to Ly. Else decrement Rx and jump to Lz
==BranchBlocks==
BranchBlocks code is made out of this blocks (which are called branch-blocks):
 branch x (
 ...
 )
which defines branch-block x (0-indexed) with code .... When branch-block is finished running and you dosen't switch to another branch-block then program will halt. First branch-block that will run is 0. Program that dosen't have branch block 0 is invalid.
===Branchblocks instructions===
Registers are 1-indexed.
 inc x
Increment register x.
 dec x
Decrement register x.
 skip x
Skip next instruction if register x is bigger than 0
 switch x
Switch to branch-block x.
==Compiling Minsky machine to Branchblocks==
 Lx inc Rx Ly
would be:
 branch Lx (
 inc Rx
 switch Ly
 )
 Lx dec Rx Ly Lz
would be:
 branch Lx (
 skip Rx
 switch Ly
 dec Rx
 switch Lz
 )
 Lx dec Rx Ly Ly
would be:
 branch Lx (
 dec Rx
 switch Ly
 )
==Branchblocks to GotoStart==
 branch x (
 ...
 )
would be:
 ?(0=x>...)
 inc x
would be:
 +(x)
 dec x
would be:
 -(x)
 skip x
 instruction
would be:
 ?(x=0>instruction)
 switch x
would be:
 =(0:x)^
===to Infinite GotoStart===
In this version
 switch x
 instructions
is converted to:
 =(0:x)?(0=block>instructions)
Where block is the current branch-block If switch is last command in the block the ? command is ommited. Program ends with ^
==Examples==
===Same program that was on Autopsy page===
 0 inc 1 3
 1 inc 1 4
 2 inc 2 2
 3 inc 1 1
 4 dec 1 5 6
 5 inc 2 4
 6 dec 1 6 6
would become:
 branch 0 (
 inc 1
 switch 3
 )
 branch 1 (
 inc 1
 switch 4
 )
 branch 2 (
 inc 2
 switch 2
 )
 branch 3 (
 inc 1
 switch 1
 )
 branch 4 (
 skip 1
 switch 5
 dec 1
 switch 6
 )
 branch 5 (
 inc 2
 switch 4
 )
 branch 6 (
 dec 1
 switch 6
 )
And then would become:
 ?(0=0>+(1)=(0:3)^)
 ?(0=1>+(1)=(0:4)^)
 ?(0=2>+(2)=(0:2)^)
 ?(0=3>+(1)=(0:1)^)
 ?(0=4>?(1=0>=(0:1)^)-(1)=(0:6)^)
 ?(0=5>+(3)=(0:4)^)
 ?(0=6>-(1)=(0:6)^)
In Infinite GotoStart:
 ?(0=0>+(1)=(0:3))
 ?(0=1>+(1)=(0:4))
 ?(0=2>+(2)=(0:2))
 ?(0=3>+(1)=(0:1))
 ?(0=4>?(1=0>=(0:1))?(0=4>-(1)=(0:6)))
 ?(0=5>+(3)=(0:4))
 ?(0=6>-(1)=(0:6))^
Category:Proofs
Goto Considered Harmless

Goto Considered Harmless is an esoteric programming language created by User:Ninesquared81. It is named after the conditional jump operation, which is the language's only control flow construct.
==Language==
The language has 4 core operations and 3 I/O operations, for a total of 7. The only available memory is an unbounded array of signed 64-bit cells. The language also exposes an instruction pointer and data pointer to the user, hereafter referred to as ip and dp, respectively.
Instruction	Description
? 	If the current cell is zero, increment dp, otherwise, offset ip by current cell value.
< 	Swap the current cell with the previous cell, then decrement dp.
+ 	Add value of dp to current cell.
- 	Subtract value of dp from current cell.
, 	Read a single character from stdin and store it in the current cell.
. 	Print the value of the currrent cell as a character.
# 	Print the value of the current cell as an integer.
All other characters are ignored. Note that although these characters are ignored, they are not entirely insignificant, since ? makes a relative jump and ip points directly into the source string, so non-instruction characters count towards the characters being jumped over.
The ? instruction can set ip as an invalid index. If ip becomes negative, it is reset to zero before the next instruction is evaluated. If it is set to some value past the end of the program's source string, the program will exit.
==Example programs==
===Infinite loop===
 ?-?
Explanation: The 0th cell is initially 0, so ? skips to cell 1. Cell 1 is set to 0 - 1 = -1, and so ? jumps back to the start of itself and loops forever.
===Truth-machine===
 ????????????????????????????????????????????????,-#
 ?????????????+? <<<<<<<<<<<<<<<<
 <<<<<<<<<<<<<<<<<<<<<<<<<<<-+#-?
Note: the space (or some other character) on the second line is required.
Explanation: We increment dp to point at cell 48, which receives the user's input. dp (48) is then subtracted from this, leaving either 0 or 1. In the case of 0, dp is again incremented to 61, otherwise it stays at 48. At ?+? (middle of second line), for input 0, cell 61 is set to 61, which is used to jump out of the program (which exits the program). If the input was 1, however, the + instruction is jumped over, and ip skips over only the space character (since the current cell is still 1). Then, dp is decremented to 5, with cell 5 now containing 1. 5 is subtracted and then added to the cell, leaving it as 1 (the reason for this will become clear soon). The value in the cell is then printed as a number. 5 is subtracted from the cell again, leaving it as -4, which is used as the offset for the jump in the ? instruction, which lands ip back to just before the + instruction. Of course, 5 is added to the cell again, restoring the value of 1, which is printed, then 5 is subtracted, ? jumps back to +, etc.
==External resources==
* Reference implementation (C)
Category:Languages
Category:2023
Category:Implemented
Category:Cell-based
Gotohell

Gotohell is a variation of C that disallows any flow control or function definitions (besides main), and focuses on defining labels and using the goto statement. switch statements are not allowed.
if statements can only be used in the following way:
if(condition) goto label; 
== Turing Completeness ==
Gotohell is a bounded-storage machine as it is a subset of C, which has a limited amount of memory.
Note: if unbounded integers are allowed in an int, then it's Turing-complete, 'cause you can use malloc
==Examples==
===Brainfuck interpreter with auto-extending memory===
#include <stdio.h>
int cs[255];
int csp = 0;
int* tape;
int tp = 0, cmsize = 3;
#define PUSH(x) cs[++csp] = x
#define POP cs[csp--] 
const char* program="YOUR PROGRAM HERE";
int main(int argc, char** argv){
 tape=malloc(sizeof int*cmsize);
	gets(program);
	int idx = 0;
	loop:
		if(program[idx] == '>') goto tr;
		if(program[idx] == '<') goto tl;
		if(program[idx] == '+') goto plus;
		if(program[idx] == '-') goto minus;
		if(program[idx] == '[') goto bloop;
		if(program[idx] == ']') goto endbloop;
		if(program[idx] == '.') goto print;
		if(program[idx] == ',') goto input;
		goto exit;
 extend:
 int nmsize=cmsize<<1, *oldtape=tape, cindex=0;
 tape=malloc(nmsize*sizeof int);
 tmp:
 if(cindex>=cmsize)goto endl;
 tape[cindex]=oldtape[cindex];
 cindex++;
 goto tmp;
		tr:
			tp++;
 if(tp>=cmsize)goto extend;
			goto endl;
		tl:
			tp--;
			goto endl;
		plus:
			tape[tp]++;
			goto endl;
		minus:
			tape[tp]--;
			goto endl;
		bloop:
			if(tape[tp] > 0) goto t;
			int loopP = 1;
			s:
				if(loopP == 0) goto endl;
				if(program[++idx] == '[') goto i;
				if(program[++idx] == ']') goto d;
				goto s;
				i: loopP++; goto s;
				d: loopP--; goto s;
			t:
				PUSH(idx);
			goto endl;
		endbloop:
			int lindex = POP;
			if(tape[tp] > 0) goto j;
			goto endl;
			j: idx = lindex; PUSH(lindex);
			goto endl;
		print:
			putchar(tape[tp]);
			goto endl;
		input:
			tape[tp] = getchar();
			goto endl;
		endl:
			idx++;
			goto loop;
	exit:
}
Input is taken through stdin.
Category:Languages Category:Esoteric subset Category:Bounded-storage machine
Gototape

Gototape is a Turing-complete language on a biderectional tape where each cell is a int. every cell is by deafault 0. There is no explicit input or output. At the end of the programme is finished, it prints the entire tape (in the format " int int int int...", and removes the first and last chain of infinite 0s.
the command format goes as follows
<command name, which is number> <the current number on the cell that the pointer is pointing to> <what number to overwrite to the cell> <what cell they should go to, according to the current cell and how far left or right they should go, designated by an int> <what command number they should go to>
The pointer is by deafaut in the 0th cell. "X" is the halt state
===Truth machine===
 
0 0 0 0 X
0 1 1 1 2
2 0 1 1 2
 
the input line can be 
-1 0 1 0 0
meaning a 1
or 
-1 0 0 0 0
meaning 0
Gott

Gott is an esoteric programming language that uses only for loops. It stores memory only as non-nested arrays of 4-bytes integers.
== Syntax/Functions ==
Gott programs are ASCII text files, formatted in lines. Each line can begin with one of several built-in functions, a memory reassignment, or a looping structure. All built-in functions are lowercase and often abbreviations of their functions. The following is a complete list of all built-in functions and their usage.
Function	Description
print 	Prints the rest of the line as ASCII text. Does not print the following newline.
printnum	Prints out the computed value of its argument, which can be a variable or an expression evaluating to a number.
newln 	Prints a newline character, \n.
exit 	Simulates an EOF for use in interactive mode.
def 	Reserves memory for and defines the value of a variable.
range 	Returns a series of integers from its first argument to its second.
= 	Used to separate the address of a block of memory and the value to be assigned there (e.g, x[0] = 5).
== Variables == 
Every variable is an array of 4-byte integers. The variable's size must be declared at the time it is reserved, and cannot be changed. A variable can also be an array with only one item, in which cane no index is required. Variables can be indexed from the start with numbers 0 and greater, and from the back with any negative number. For example,
array[3] in a 10-place array would be item 4 of the array (indexing from 0). array[-3] would be the length of the array minus the index: item 8 of the array.
Variables can be declared and reassigned as follows:
def var[5] 1, 0, 0, 0, 0
var[2] = 4*var[0] + 1 # 1, 0, 3, 0, 0
Note: + and - must preceded and followed by spaces.
== Control Flow ==
The only flow control utility is a for loop, which can be implemented in two different ways. Given an array Z, here are the two kinds of for loops:
for(Z): # Repeats the following indented block for the number of times in the first position of x.
for(i in Z): # Repeats the following indented block iterating i along each member of Z until the end of Z is reached.
== Example Programs ==
=== Hello World ===
print Hello, World!
newln
=== 99 Bottles of Beer ===
print 99 bottles of beer on the wall,
newln
print 99 bottles of beer.
newln
print Take one down, pass it around,
newln
decl values[98] range 98, 1
for(bottles in values):
	printnum bottles
	print bottles of beer on the wall.
	newln
	printnum bottles
	print bottles of beer on the wall,
	newln
	printnum bottles
	print bottles of beer.
	newln
	print Take one down, pass it around,
	newln
print no more bottles of beer on the wall.
newln
Gottlob

Gottlob is an imperative programming language with unusual syntax created by Matthew Dockrey in 2019. It has unusual syntax, based on Gottlob Frege's logic notation from his 1879 book “Begriffsschrift: A formula language, modeled on that of arithmetic, of pure thought”. The source code is written not in plain text, but drawn as a tree in two dimensions, similar to Plankalkül or early drafts of APL. There is an implementation with a specialized interactive editor for the source code.
== External resources ==
* Introduction by creator
* Short video showing the editor
Category:Languages
Category:2019
Category:Thematic
Category:Implemented
Govnom Srat' Pomojet Letat'

Govnom Srat' Pomojet Letat' is a programming language created by User:Xi-816. It is very simple, and has only 6 commands.
At start you have 1 register with value 0. It can store the value from 0 to 255. You can increment the register, output it, and create a new timeline. If you create it, you now have copy of your register, and you can store 2 bytes of information. Also, you can go past, or future.
== Commands ==
Command	Timeline 	Description
+ 	t(N) = (N+1) % 256	Increments a register
. 	t(N) = N + out(N) 	Outputs as an ASCII character
; 	t(N) = T + N 	Creates a new timeline
$ 	Tc = Tc - 1 	Go past
# 	Tc = Tc + 1 	Go future
^ 	T = T - N 	Delete a timeline
== Hello World! ==
 ++++++++++
++++++++++
++++++++++
++++++++++
++++++++++
++++++++++
++++++++++++.
+++++++++++++++;
++++++++++
++++.+++++++..+++.;
++++++++++++++++++++
++++++++++++++++++++
++++++++++++++++++++
++++++++++++++++++++
++++++++++++++++++++
++++++++++++++++++++
+++++++++++++++++++++++++
++++++++++++++++++++
++++++++++++.$$.#.+++.$+++++++++++++
;$+++++++++++.#.##+.
Category:Languages
GraNoLa/M

GraNoLa/M is a programming language in which a directed graph is the
only data type. It was Chris Pressey's entry for the 2002 Esoteric Awards.
==External resources==
*
*Docker image for running GraNoLa/M
*GraNoLa/M entry for 2002 Essies
Category: Languages
Category: Implemented
Category: 2002
Grain

Grain is a theoretical programming language in which all functions can be infinitely recursively derived from combinations of other functions.
User:Grom believes it could be possible to implement such a language in an efficient and relatively deterministic manner without rounded floating points.
Essentially the language boils down to two concepts/problems:
The first is how to create varied functional effects from large integers. This will be achieved via a function called the granulator (herein simply "𝔾").
The second is to, given any number A, produce an ordered combination of functions (integers) that when applied successively (ie: f(g(h(j(x)))) ) maps the domain of 𝔾(A) to the codomain of 𝔾(A)
ie:
A(x) = f(g(h(i(x))))
𝕄(A)(x) = f(g(h(i(x))))
𝕄(A) = (f, g, h, i)
𝕄'(f(x), g(x), h(x), i(x)) = A(x)
The function that produces this combination of functions will herein be referred to as the Master Function, or simply "𝕄".
== Formal Definition of 𝕄 and 𝔾 ==
For all integers x, 
- 𝔾(𝕄(x)) is a function which exists in the co-domain of 𝔾.
- 𝔾(x) shares the same mapping as 𝔾(𝕄(x))
- 𝕄(x) does not contain x
More succinctly:
∀x∈ℤ (∀n∈ℤ 𝔾(x)(n) = 𝔾(𝕄(x))(n) ⋀ (𝕄(x) ⋂ x = ∅) ⋀ (𝔾(𝕄(x)) ⋂ 𝔾 ≠ ∅))
== Properties of the Master Function ==
=== - reversible ===
=== - O(1) time ===
(The resulting function composition can be computed mathematically (as opposed to iteratively) directly from func with 𝕄(func) )
== Evidence of viability ==
To prove that some non zero amount of viable Master Functions exist, consider some 𝕄 wherein:
∀x∈ℤ 
𝔾(x) ∈ {f(n) = n+1, g(n) = n-1, h(n) = n+2, i(n) = n-2}
∀x∈ℤ (𝔾(x)(n) = n+1 = f(n) | 𝔾(𝕄(x))(n) = g(h(n)) = n+2-1 = n+1)
∀x∈ℤ (𝔾(x)(n) = n-1 = g(n) | 𝔾(𝕄(x))(n) = f(i(n)) = n-2+1 = n-1)
∀x∈ℤ (𝔾(x)(n) = n+2 = h(n) | 𝔾(𝕄(x))(n) = f(f(n)) = n+1+1 = n+2)
∀x∈ℤ (𝔾(x)(n) = n-2 = i(n) | 𝔾(𝕄(x))(n) = g(g(n)) = n-1-1 = n-2)
This is not a very interesting 𝕄 or 𝔾, not only is 𝔾 of finite cardinality, but ∀x∈ℤ card|𝕄(x)| = 2.
GrainFimple

GrainFimple is an esoteric programming language by User:Zzo38 based on Brainfuck and BF-RLE, and which can be used to make games.
==Header==
Each program must start with a header containing the following fields:
* SPEED=number of frames per second.
* CHARSET=ASCII7 or DOSASCII.
** If ASCII7, then 32-126 are printable characters, 0-31 and 127 are blank, and 128-255 are reverse-video. 
** If DOSASCII, then 0-255 are DOS ASCII symbols.
* ROWS=number of rows in video memory.
* COLS=number of columns in video memory.
* MEMORY=bytes of normal memory required by the program.
* START indicates the end of the header and the start of program execution.
==Commands==
* All BF-RLE commands except . and ,.
* ; = Read input of buttons: Bit0=A Bit1=B Bit2=SELECT Bit3=START Bit4=RIGHT Bit5=LEFT Bit6=UP Bit7=DOWN.
* : = Switch between normal memory and video memory.
* ? = Get the value y at the current memory position and the value x at the next memory position and play a sound with frequency (256*y+x) Hz. If y and x are both zero then stop the sound.
* ! = Breakpoint.
* ~~ = Comment until end of line.
* $ = Next frame.
* ^ = Number of frames passed since last $ (used to test speed).
* " = Set memory to the ASCII character after the quotation mark.
* & = Compute NAND of the values at the current and next memory positions.
==Example==
 SPEED=30
 CHARSET=ASCII7
 ROWS=10
 COLS=16
 MEMORY=256
 START
 :"P>"R>"E>"S>"S>" >"S>"T>"A>"R>"T>"!:
 +[;>+5<&>[-]-<&-5]
 :<8"H>"e>"l>"l>"o>" >"W>"o>"r>"l>"d>"!:
 +[]
Category:2006 Category:Languages
Graph

A graph is a net or web. It can have directed or undirected edges (also known as lines or links) that connect nodes. Its presentation by picture is usually arrows connecting dots. Other ways of expressing a graph are list of connecting nodes from each node and a table where a 1 signifies connection between nodes at the ends of vertical and horizontal rows, and 0 means no connection, so the representation has a bitmap. A graph with intermediary states between connection and no connection, decimal numbers between 0 and 1, grayscales, is a weighed graph.
Most languages have graphs in some form even if the developers did not think them at all.
Some languages using graphs very directly and deliberately are Cvlemar and Eodermdrome.
A directed graph is one that has directed edges. Normally, duplicate edges between the same nodes in the same direction aren't allowed because it is a set rather than a multiset. If duplicate edges are allowed, it is called a multigraph (a directed multigraph if the edges are directed, otherwise it is a undirected multigraph).
A planar graph is a graph that can be drawn on a 2D plane without the lines crossing each other.
A RDF graph is a directed graph where:
* There are many types of edges, where the type of the edge is specified as a URI.
* Each node is either labeled or unlabeled, or a "literal node".
* A labeled node is labeled by a URI, and there is only one node with each URI.
* An unlabeled node has no label and can be defined only by how it is wired to the rest of the graph.
* A literal node contains a pair consisting of a string of Unicode codepoints (ranging from U+0001 to U+10FFFF, except surrogates, U+FFFE, and U+FFFF) and a URI.
* A literal node cannot have any edges leading out of it, and does not necessarily have other properties of a node either.
== See Also ==
:Category:Graph-based
Category:Data Types and Structures
Graph Oriented Fictional Computer

Graph Oriented fictional computer is a fictional computer with a graph-based memory as opposed to a linear one. It was designed by User:Andriy who also implemented an emulator in Java. Each node is referred to by a capital English letter, and each node can have up to 26 child nodes which are also referred as a capital English letter. In the context of this fictional computer, the address of a node refers to the path you have to go through in order to reach it. For example child C of child B of node A is a node with the address ABC. Using the command redirect, it's possible for a node to have multiple correct addresses. Each node can store a one byte value. However, values that take larger space can also be stored by utilizing the child node C, then CC, and so on. It's possible to store strings, 8 bit integers which can be stored as big endian or as little endian, and fractions (like double variables in Java).
This fictional computer can be considered as having one esoteric programming language or two closely related ones. The first one consists of the commands typed into the command line of the fictional computer. The second one utilizes the graph to store the code in it. The first instruction is stores in node I, and the parameters are stored in children nodes A, B, ... of the node with the instruction. With the exception of conditions, the next instruction will be executed from child I. If the instruction is a condition, the code will branch out depending on the condition. If the child node which is meant to store the next instruction doesn't exist, the fictional computer will interpret it as if it has reached the end of the code, halt execution and return control to the user. The program is able to modify any part of the graph, including the part of the graph where the code is stored, making it self-modifying code.
In order to build a graph containing the code of the second esoteric programming language, you need to use commands from the first one. However, typing many commands can be exhausting, especially if you made a mistake somewhere, which is why it's recommended to type all the commands in a txt file, and run the jar file in the shell of your computer with the txt file as a parameter. Once you are done building the graph with the code, the command RUN will execute it.
You can use the commands HELP and MAN to get useful information about the fictional computer. The command HELP will explain how the fictional computer works, while the command MAN will give a list of instructions. All instructions that can be typed in the command line are written by all-caps, while all commands that can be included in the graph are numbered. In the context of this fictional computer, a node containing a command means a node containing a byte value corresponding to that of the command. The parameters are stored as strings. If you want to read useful information about a certain command, you can type MAN followed by the number of that command, or it's name. for example MAN GET, and MAN 2 will both print out useful information about the command GET.
Category:2023
Category:Implemented
Category:Turing complete