4

我创建了自己的编程语言，可以编译成图灵机指令，我想知道如何实现if(a>b) do _ end. 这是语言的定义（也可在此处获得）

变量以任意宽度动态分配，因此可以具有任意大的整数

每行可以做三件事之一，它可以调用一个函数（修改它的参数），启动一个while循环（这实际上更像是一个for循环），或者分配一个变量。

可用的函数有incr（加一，可能溢出），decr（减一，可能溢出），pop（从变量中删除最后一位），first（将变量中最重要的 0 更改为 1）和frost（更改最显着 1 到 0）。

while 循环具有以下语法，

while a <func> {
    _
}

基本上每次循环它都会<func>直到a出现错误情况。错误情况如下，incr全first1，decr全frost0，pop去掉最后一位。在 while 循环后，循环变量的所有位incr或所有位都将为 0，与and相反。While 循环必须在函数调用时结束，并且它们会在每次运行后删除其中包含的所有变量。frostfirstdecr

赋值可以根据语法做一些不同的事情。a=b意味着将变量复制b到变量所拥有的空间中，a如果b长度超过a这会导致未定义的行为，除非a是创建了最新的变量。a=b,5分配b给a左侧五个填充位（设置为零），再次溢出导致未定义的行为，除非a是创建的最新变量。a=a,0归零a。最后a=5,3将分配5 % 2**3到a3 位。

现在我可以if(a != 0) do _ end用

while a decr {
    _
    t=0,1
    while a incr {
        incr(t)
    }
    incr(t)
}

我的问题是如何实现其他 if 语句，如if(a==b),if(a!=b)和if(a>b)

作为第二个问题是这种语言图灵完备，我相信基于这个答案编程语言是否有最低标准是图灵完备的？. 我知道语言满足 1 到 5，但我不确定 6。

4

1 回答 1

0

（如果我对循环或 incr/decr 行为有错误的假设，请告诉我，这会改变我的答案）

您的原始代码if(a!=0)似乎永远循环。事实上，它正在这样做while(a) do _ end是因为它要么无限循环要么根本不循环。最后t不会存在于循环之外，并且似乎不会在循环内部使用，即使它看起来像您要捕获的值（比较时为真/假）。

你没有注释语法，所以我会// comment在需要的地方加入 / c 样式的注释。

也许像这样的东西......

如果 (a > 0) 做 _ 结束

// if (a > 0) do _ end
_a = a
while _a decr {
    // overflow iif _a= 0
    _ // do something
    _a = 0
    frost( _a ) // only function calls at end of loops
}

如果（a == 0）做_结束

// if (a == 0) do _ end
_a = a
result = 1,1
while _a decr {
    // overflow iif _a= 0
    _a = 0
    frost( result ) // only function calls at end of loops
}
while result decr {
    // overflow iif result = 0
    _ // do something
    frost( result ) // exit loop
}

正如您所注意到的，该模式对于非零检查很简单 - 递减它，如果您没有溢出（技术上是下溢），那么您正在处理 1 或更大的东西。Trick 正在退出while，您可以通过使用 decr 测试并在退出时将要测试的变量设置为 0 来做到这一点。为此，您的frost函数是合适的，因为对于 0 的目标变量，它不会修改结果，而 1 的目标变为 0，例如 inresult的用法。

您的文档说函数必须标记循环的结束，而不是赋值或另一个循环，但您自己的示例与此不一致，请注意。

我正在为剩余的测试条件做一个例子：a > b和a == b; 其他可以从这两个逻辑反转/非运算符派生，您在上面看到使用result.

如果（a == b）做_结束

// if( a == b ) do _ end
a_cond = a
b_cond = b
// step 1: a_cond = a - b
while b_cond decr {
    decr(a_cond)
}
// step 2: if (a_cond == 0)
result = 1,1
while a_cond decr {
    // overflow iif a_cond = 0
    a_cond = 0
    frost( result ) // only function calls at end of loops
}
while result decr {
    // overflow iif result = 0
    _ // do something
    frost( result ) // exit loop
}

如果 (a > b) 做_结束

在制品。将类似于 (a==b) 的情况

于 2016-06-29T07:23:14.110 回答