1
$\begingroup$

Let's consider bit string as a program for some computational model. If after $k$ steps program represented by number $n$ halts and outputs bit string $s$, then complexity of s is (n+1)*k. For example complexity of result of program $101$ after 3 steps is (5 + 1)*3 = 18. Have this or similar complexity measure been studied somewhere? What's its name?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.