A program using O(1) space is computationally equivalent to a finite automata. | 图灵班论坛

Your browser does not seem to support JavaScript. As a result, your viewing experience will be diminished, and you have been placed in read-only mode.

Please download a browser that supports JavaScript, or enable it if it's disabled (i.e. NoScript).

诟屍

A program using O(1) space is computationally equivalent to a finite automata.

From this post
诟屍 | , 最后由编辑

• 0
没有人

Proof??? 在这个问题里应该怎么看？评论第一条认为是错的
没有人 | , 最后由编辑

• 0
诟屍

@没有人楼主认为不能修改输入，那肯定是不能 O(1) 实现的
下面回复的人认为可以先修改输入，之后再修改回来，所以认为楼主是错的
所以他们的讨论就是在瞎扯 233
诟屍 | , 最后由编辑

• 0
诟屍

不过有个人提到的 Random-access stored-program machine 挺有趣
诟屍 | , 最后由编辑

• 0

fa2 • 帖子 4 • 浏览 1840

登录后回复