英文:
Determining a program's execution time by its length in bits?
问题
I understand your request. Here is the translation of the text you provided:
这是我在阅读停机问题、考拉兹猜想和科尔莫哥洛夫复杂性时突然想到的一个问题。我尝试搜索类似的内容,但未能找到一个特定的主题,可能是因为它没有太大的价值,或者只是一个琐碎的问题。
为了简单起见,我将提供三个程序/函数的示例。
函数一(s):
返回 s
函数二(s):
while (True):
打印 s
函数三(s):
for i 从 0 到 10^10:
打印(s)
所以我的问题是,是否有一种方式可以形式化程序的长度(比如用于描述它的位数),以及程序使用的内部内存,以确定决定程序是否终止或永远运行所需的最小/最大次数/步骤。
例如,在第一个函数中,程序不会改变其内部内存,在一些时间步骤后终止。
在第二个示例中,程序永远运行,但程序也不会改变其内部内存。例如,如果我们考虑所有与程序二相同长度的程序,它们不会改变其状态,我们是否可以确定一个步骤的上限,如果超过这个上限,我们可以得出结论这个程序永远不会终止?(如果不能,为什么?)
在最后一个示例中,程序会改变其状态(变量 i)。因此,每一步的上限可能会改变。
[简而言之]
科尔莫哥洛夫复杂性提出了一种找到对象(如文本片段)的(描述性)复杂性的方法。我想知道,鉴于用于描述程序在运行时使用的内存空间的正式方式,我们是否可以计算一个最大步数,如果超过这个步数,我们就可以知道这个程序是否会终止还是永远运行。
最后,我想建议您一些可能对我找出我究竟在寻找什么有用并帮助我的来源。谢谢。(对不起,我的英语不是母语。我希望我表达清楚了。)
英文:
This is a question popped into my mind while reading the halting problem, collatz conjecture and Kolmogorov complexity. I have tried to search for something similar but I was unable to find a particular topic maybe because it is not of great value or it could just be a trivial question.
For the sake of simplicity I will give three examples of programs/functions.
function one(s):
return s
function two(s):
while (True):
print s
function three(s):
for i from 0 to 10^10:
print(s)
So my questions is, if there is a way to formalize the length of a program (like the bits used to describe it) and also the internal memory used by the program, to determine the minimum/maximum number of time/steps needed to decide whether the program will terminate or run forever.
For example, in the first function the program doesn't alter its internal memory and halts after some time steps.
In the second example, the program runs forever but the program also doesn't alter its internal memory. For example, if we considered all the programs with the same length as with the program two that do not alter their state, couldn't we determine an upper bound of steps, which if surpassed we could conclude that this program will never terminate ? (If not why ?)
On the last example, the program alters its state (variable i). So, at each step the upper bound may change.
[In short]
Kolmogorov complexity suggests a way of finding the (descriptive) complexity of an object such as a piece of text. I would like to know, given a formal way of describing the memory-space used by a program (computed in runtime), if we could compute a maximum number of steps, which if surpassed would allow us to know whether this program will terminate or run forever.
Finally, I would like to suggest me any source that I might find useful and help me figure out what I am exactly looking for.
Thank you. (sorry for my English, not my native language. I hope I was clear)
答案1
得分: 0
如果一个确定性图灵机两次进入完全相同的配置(我们可以通过保持迄今为止看到的配置的跟踪来检测),那么我们立即知道该图灵机将永远循环。
如果事先已知确定性图灵机不可能使用超过某个固定的输入磁带数量,那么该图灵机必须明确停止或最终进入某个已经访问过的配置。假设该图灵机最多可以使用k个磁带单元,磁带字母是T,状态集是Q。那么有(|T|+1)^k * |Q|个唯一的配置(长度为k的(T并空白)字符串数量乘以状态数量),根据抽屉原理,我们知道一个需要这么多步骤的图灵机必须进入某个它之前已经访问过的配置。
第一:因为我们知道这个函数不使用内部内存,所以我们知道它要么停止,要么永远循环。
第二:因为我们知道这个函数不使用内部内存,所以我们知道它要么停止,要么永远循环。
第三:因为我们知道这个函数只使用固定数量的内部内存(如34位),所以我们可以在不到2^34次循环中确定对于任何给定的输入s,TM是否会停止。
现在,知道一个TM要使用多少磁带,或者一个程序要使用多少内存,不是一个TM可以解决的问题。但如果你有一个预言者(像一个能够做出证明的人)告诉你内存的正确的固定上限,那么停机问题是可以解决的。
英文:
If a deterministic Turing machine enters precisely the same configuration twice (which we can detect b keeping a trace of configurations seen so far), then we immediately know the TM will loop forever.
If it known in advance that a deterministic Turing machine cannot possibly use more than some fixed constant amount of its input tape, then the TM must explicitly halt or eventually enter some configuration it has already visited. Suppose the TM can use at most k tape cells, the tape alphabet is T and the set of states is Q. Then there are (|T|+1)^k * |Q| unique configurations (the number of strings over (T union blank) of length k times the number of states) and by the pigeonhole principle we know that a TM that takes that many steps must enter some configuration it has already been to before.
one: because we are given that this function does not use internal memory, we know that it either halts or loops forever.
two: because we are given that this function does not use internal memory, we know that it either halts or loops forever.
three: because we are given that this function only uses a fixed amount of internal memory (like 34 bits) we can tell in fewer than 2^34 iterations of the loop whether the TM will halt or not for any given input s, guaranteed.
Now, knowing how much tape a TM is going to use, or how much memory a program is going to use, is not a problem a TM can solve. But if you have an oracle (like a person who was able to do a proof) that tells you a correct fixed upper bound on memory, then the halting problem is solvable.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论