brainfuck详解

最近长城杯的杂项涉及到brainfuck，学习记录一下。

brainfuck被称为最小的图灵完备语言。

wiki百科

图灵完备性(Turing completness)

在可计算性理论(computability theory)中，图灵等价指的是：对于两个计算机A和B，如果A可以模拟B，B可以模拟A，就称他们是图灵等价的。

根据“丘奇-图灵”理论，图灵机是表达能力最强大的计算系统，对现实世界中的任何计算机，都可以用图灵机来模拟它。腻不腻害！

如果某个系统能够模拟图灵机，那么就称该系统是图灵完备的。

可不是，都能完全模拟图灵机了可不是就完备了。

图灵完备语言

套用上面的定义，如果一个编程语言可以完全模拟图灵机，那么它就是图灵完备的。

图灵机的定义是很简单的，仅有少量操作和一种数据类型。所以很容易验证某一个语言是图灵完备的。写个模拟器呗。

大部分编程语言都是图灵完备的，因为他们需要解决各种问题的通用能力，而这正是图灵机所具备的。确实存在一些语言不是图灵完备的，他们通常是被设计用来解决某些特殊的问题，比如，你猜对了，SQL[2]以及正则表达式。

以经验来看，凡带有分支，跳转能力，并且支持数组状数据结构的语言基本上就是图灵完备的。

图灵机

图灵机，又称图灵计算、图灵计算机，是由数学家阿兰·麦席森·图灵(1912~1954)提出的一种抽象计算模型，即将人们使用纸笔进行数学运算的过程进行抽象，由一个虚拟的机器替代人们进行数学运算。

所谓的图灵机就是指一个抽象的机器，它有一条无限长的纸带，纸带分成了一个一个的小方格，每个方格有不同的颜色。有一个机器头在纸带上移来移去。机器头有一组内部状态，还有一些固定的程序。在每个时刻，机器头都要从当前纸带上读入一个方格信息，然后结合自己的内部状态查找程序表，根据程序输出信息到纸带方格上，并转换自己的内部状态，然后进行移动。

图灵机

Turing Machine

介绍了一些理论的东西，我们来看看brainfuck的基本操作：

我们将这8个指令用c语言模拟一下，大概就是这样：

这里注意，bf里 + 和 - 是可以overflow的，比如255+1 = 0，0-1 = 255。从这里也可以看出bf里的数值都是无符号的。

> 指针右移一位指向下一个字节 < 指针左移一位指向上一个字节，但是由于指针两边不会无限长，所以会出现溢出空间的情况，编译器会报错。

直接看题目：

1
>+++++++++[<+++++++++++++>-]>+++[<+++++++++++++++++++++++++++++++++++++>-]>++[<+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>-]>++++[<+++++++++++++++++++++++++++++>-]>+++[<+++++++++++++++++++++++++++++++++++++++++>-]+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>++++++[<+++++++++++++++++++>-]>++[<+++++++++++++++++++++++++++++++++++++++++>-]>+++++++++++[<+++++++++++>-]>++[<+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>-]>+++++++[<+++++++++++++++>-]+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>+++++[<+++++++++++++++++++>-]>++++++++[<+++++++++++>-]>++++++[<+++++++++++++++++>-]>+++++++[<+++++++++++++++>-]+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>++[<+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>-]>+++++[<+++++++++++++++++++>-]>+++++++[<+++++++>-]>++++++++[<+++++++++>-]>+++++[<+++++++++++++++++++>-]>++++[<+++++++++++++>-]>+++++[<+++++++++++++++++++>-]+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>++++++[<++++++++>-]+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>+++++++[<+++++++++++++++++>-]>++[<+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>-]>+++++++[<+++++++++++++++>-]>+++++++++[<+++++++++++++>-]>++++++[<+++++++++++++++++>-]>+++[<+++++++++++>-]>+++++[<+++++++++++++++++++>-]>++++++++++[<++++++++++++>-]>++++++[<+++++++++++++++++>-]>+++++++[<+++++++++++++++>-]+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>++[<+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>-]>+++++[<+++++++++++++++++++++++++>-]+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>>++++++[<+++++++++++++++++++>-]<.>>++++++[<+++++++++++++++++++>-]<.>>+++[<+++++++++++++++++++++++++++++++++++++>-]<.>>++++++[<+++++++++++++++++++>-]<.>

可以看到最后有五个输出，输出的值为error。

前面有很多操作，但是都没有进行输出，只输出了个没啥用误导人的东西。

所以我们就要看它操作的内存空间的情况，这里用到脚本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
def interp(code):
    data = [0 for i in range(1000)]
    pc = 0
    ptr = 0
    skip_loop = False
    bracket_count = 0
    stack = []
    while pc < len(code):
        c = code[pc]
        if skip_loop :
            if c =='[':
                bracket_count+=1
            elif c==']':
                bracket_count -=1
                if bracket_count==0:
                    skip_loop =False
            pc+=1
            continue
        if c == '>':
            ptr +=1
            pc +=1
        elif c == '<':
            ptr -=1
            pc +=1
        elif c == '+':
            data[ptr] +=1
            pc +=1
        elif c == '-':
            data[ptr] -=1
            pc +=1
        elif c == '.':
            for a in range(len(data)):
                if chr(data[a]) != '}':
                    print(chr(data[a]),end="")
                else:
                    print('}')
                    exit()
            pc +=1
        elif c == ',':
            pc +=1
        elif c == '[':
            if data[ptr] == 0:
                #nonlocal bracket_count,skip_loop
                bracket_count = 1
                skip_loop = True
                pc+=1
            else:
                pc+=1
                stack.append(pc)
        elif c == ']':
            if data[ptr] == 0:
                pc+=1
                stack.pop()
            else:
                pc = stack[len(stack)-1]
 
#interp('++++.>>++.')
#interp('+++++.>++.[-<+>]<.')
interp('>+++++++++[<+++++++++++++>-]>+++[<+++++++++++++++++++++++++++++++++++++>-]>++[<+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>-]>++++[<+++++++++++++++++++++++++++++>-]>+++[<+++++++++++++++++++++++++++++++++++++++++>-]+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>++++++[<+++++++++++++++++++>-]>++[<+++++++++++++++++++++++++++++++++++++++++>-]>+++++++++++[<+++++++++++>-]>++[<+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>-]>+++++++[<+++++++++++++++>-]+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>+++++[<+++++++++++++++++++>-]>++++++++[<+++++++++++>-]>++++++[<+++++++++++++++++>-]>+++++++[<+++++++++++++++>-]+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>++[<+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>-]>+++++[<+++++++++++++++++++>-]>+++++++[<+++++++>-]>++++++++[<+++++++++>-]>+++++[<+++++++++++++++++++>-]>++++[<+++++++++++++>-]>+++++[<+++++++++++++++++++>-]+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>++++++[<++++++++>-]+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>+++++++[<+++++++++++++++++>-]>++[<+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>-]>+++++++[<+++++++++++++++>-]>+++++++++[<+++++++++++++>-]>++++++[<+++++++++++++++++>-]>+++[<+++++++++++>-]>+++++[<+++++++++++++++++++>-]>++++++++++[<++++++++++++>-]>++++++[<+++++++++++++++++>-]>+++++++[<+++++++++++++++>-]+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>++[<+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>-]>+++++[<+++++++++++++++++++++++++>-]+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>>++++++[<+++++++++++++++++++>-]<.>>++++++[<+++++++++++++++++++>-]<.>>+++[<+++++++++++++++++++++++++++++++++++++>-]<.>>++++++[<+++++++++++++++++++>-]<.>')
#interp('+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.')


在读取到输出的时候，直接打印bf内存里的所有的字符直到 “}”。也可以在读取到输出时无操作，在函数执行完后直接打印bf的内存空间，也能打印没有输出的flag

output：

1
uozt{SrRyvig_Xfiev_1H_4_ee0mwviuf!_xfiev}
Page View
⬆︎TOP