プログラムの概念を作ったチューリングによれば、「コンピュータ言語は少なくともチューリング完全でなければプログラミング言語とは呼ばれない」という決まりがあるようです。
そして、チューリング完全な最小の言語としてbrainfuckという言語があります。
https://qiita.com/TomoShiozawa/items/25dcce1540085df71053
なんか情報系の大学の計算機理論やコンパイラ理論で「brainfuckを作ってみよう！」ってよく習うらしいですが、おじさん習ったことないぞ。brainfuckできたの1991年だもんなぁ。
しかもgithubなどで世の中に落ちているこのbrainfuckの実装はプログラムを習った学生が作っているためかどれもバグだらけじゃないか。
チューリング完全の理解も間違っている。
バグがバグを生む負の連鎖になっているので、正しいbrainfuckを作ってみました。
https://qiita.com/takl/items/6ffe14db22974b1f74ce
とりあえずここのページのコードがかなりゴールに近いしソースがわかりやすいのでここからソースをとってきて改良。
------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#if 0
#define PROG ">+++++++++[<++++++++>-]<.>+++++++[<++++>-]<+.+++++++..+++.[-]>++++++++[<++++>-]<.>+++++++++++[<+++++>-]<.>++++++++[<+++>-]<.+++.------.--------.[-]>++++++++[<++++>-]<+.[-]++++++++++."
const char * const prog = PROG;
#else
const char * const prog =
">+++++[>+++++++<-]>.<<++[>+++++[>+++++++<-]<-]>>.+++++.<++[>-----<-]>-.<++"
"[>++++<-]>+.<++[>++++<-]>+.[>+>+>+<<<-]>>>[<<<+>>>-]<<<<<++[>+++[>---<-]<-"
"]>>+.+.<+++++++[>----------<-]>+.<++++[>+++++++<-]>.>.-------.-----.<<++[>"
">+++++<<-]>>.+.----------------.<<++[>-------<-]>.>++++.<<++[>++++++++<-]>"
".<++++++++++[>>>-----------<<<-]>>>+++.<-----.+++++.-------.<<++[>>+++++++"
"+<<-]>>+.<<+++[>----------<-]>.<++[>>--------<<-]>>-.------.<<++[>++++++++"
"<-]>+++.---....>++.<----.--.<++[>>+++++++++<<-]>>+.<<++[>+++++++++<-]>+.<+"
"+[>>-------<<-]>>-.<--.>>.<<<+++[>>++++<<-]>>.<<+++[>>----<<-]>>.++++++++."
"+++++.<<++[>---------<-]>-.+.>>.<<<++[>>+++++++<<-]>>-.>.>>>[-]>>[-]<+[<<["
"-],[>>>>>>>>>>>>>+>+<<<<<<<<<<<<<<-]>>>>>>>>>>>>>>[<<<<<<<<<<<<<<+>>>>>>>>"
">>>>>>-]<<+>[-[-[-[-[-[-[-[-[-[-[-[-[-[-[-[-[-[-[-[-[-[-[-[-[-[-[-[-[-[-[-"
"[-[-[-[-[-[-[-[-[-[-[-[<->[-]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]<["
"<<<<<<<<<<<<[-]>>>>>>>>>>>>[-]]<<<<<<<<<<<<[<+++++[>---------<-]>++[>]>>[>"
"+++++[>+++++++++<-]>--..-.<+++++++[>++++++++++<-]>.<+++++++++++[>-----<-]>"
"++.<<<<<<.>>>>>>[-]<]<<<[-[>]>>[>++++++[>+++[>++++++<-]<-]>>++++++.-------"
"------.----.+++.<++++++[>----------<-]>.++++++++.----.<++++[>+++++++++++++"
"++++<-]>.<++++[>-----------------<-]>.+++++.--------.<++[>+++++++++<-]>.[-"
"]<<<<<<<.>>>>>]<<<[-[>]>>[>+++++[>+++++++++<-]>..---.<+++++++[>++++++++++<"
"-]>.<+++++++++++[>-----<-]>++.<<<<<<.>>>>>>[-]<]<<<[-[>]>>[>+++[>++++[>+++"
"+++++++<-]<-]>>-.-----.---------.<++[>++++++<-]>-.<+++[>-----<-]>.<++++++["
">----------<-]>-.<+++[>+++<-]>.-----.<++++[>+++++++++++++++++<-]>.<++++[>-"
"----------------<-]>.+++++.--------.<++[>+++++++++<-]>.[-]<<<<<<<.>>>>>]<<"
"<[<+++[>-----<-]>+[>]>>[>+++++[>+++++++++<-]>..<+++++++[>++++++++++<-]>---"
".<+++++[>----------<-]>---.<<<<<<.>>>>>>[-]<]<<<[--[>]>>[>+++++[>+++++++++"
"<-]>--..<+++++++[>++++++++++<-]>-.<+++++[>----------<-]>---.[-]<<<<<<.>>>>"
">]<<<[<+++[>----------<-]>+[>]>>[>+++[>++++[>++++++++++<-]<-]>>-.<+++[>---"
"--<-]>.+.+++.-------.<++++++[>----------<-]>-.++.<+++++++[>++++++++++<-]>."
"<+++++++[>----------<-]>-.<++++++++[>++++++++++<-]>++.[-]<<<<<<<.>>>>>]<<<"
"[--[>]>>[>+++++[>+++++[>+++++<-]<-]>>.[-]<<<<<<<.>>>>>]<<<[<++++++++++[>--"
"--------------<-]>--[>]>>[<<<<[-]]]]]]]]]]]>>]<++[>+++++[>++++++++++<-]<-]"
">>+.<+++[>++++++<-]>+.<+++[>-----<-]>.+++++++++++.<+++++++[>----------<-]>"
"------.++++++++.-------.<+++[>++++++<-]>.<++++++[>+++++++++++<-]>.<+++++++"
"+++.";
#endif
struct stack {
int* vp;
int sz;
int pos;
};
void stack_init(struct stack* a)
{
if (a == NULL)return;
a->sz = 1;
a->pos = 0;
a->vp = malloc(sizeof(int) * a->sz);
}
void stack_push(struct stack* a, int n)
{
if (a == NULL)return;
if (a->pos + 1 == a->sz) {
a->sz = a->sz * 2;
a->vp = realloc(a->vp, sizeof(int) * a->sz);
}
a->vp[a->pos] = n;
a->pos++;
}
int stack_pop(struct stack* a)
{
if (a == NULL)return 0;
if (a->pos == 0) {
return 0;
}
a->pos--;
return a->vp[a->pos];
}
const char *back(const char *ip) {
int nest = 0;
while (1) {
if (ip == prog) {
printf("invalid ']'\n");
exit(EXIT_FAILURE);
}
switch (*--ip) {
case '[':
if (nest == 0) return ip;
--nest;
break;
case ']':
++nest;
break;
default:
break;
}
}
}
const char *forth(const char *ip) {
int nest = 0;
while (1) {
switch (*ip++) {
case '\0':
printf("invalid '['\n");
exit(EXIT_FAILURE);
case '[':
++nest;
break;
case ']':
if (nest == 0) return ip;
--nest;
break;
default:
break;
}
}
}
int main() {
struct stack ls, rs;
stack_init(&ls);
stack_init(&rs);
int cell = 0;
const char *ip = prog;
while (1) {
switch (*ip++) {
case '\0':
return 0;
case '+':
++cell;
break;
case '-':
--cell;
break;
case ';':
printf("[%d]", cell);
fflush(stdout);
break;
case '.':
printf("%c", cell);
fflush(stdout);
break;
case ',':
cell = getchar();
break;
case '>':
stack_push(&ls, cell);
cell = stack_pop(&rs);
break;
case '<':
stack_push(&rs, cell);
cell = stack_pop(&ls);
break;
case '[':
if (cell == 0) ip = forth(ip);
break;
case ']':
if (cell != 0) ip = back(ip - 1) + 1;
break;
default:
break;
}
}
}
------------------------------
このbrainfuckはチューリング完全な言語で、チューリング完全な言語を実装できる言語もチューリング完全らしいです。
ということで、C言語もチューリング完全ですね。
きっと大学だと「brainfuckを実装し、C言語がチューリング完全であることを示せ」とか課題が出るんだろうな。
