0
$\begingroup$

Say you have some virtual machine with < 100 numbered opcodes that fully specify its behaviour. Is there an easy way to order and enumerate all possible programs of less than n instructions, the result being that a particular number refers to a particular program? Preferably with natural numbers and short programs at the begining.

As this list would be combinatorially large, it would be helpful to assign these numbers without running the programs or loading them into memory.

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ Say $m$ is the number of opcodes, then the natural thing would be to encode programs with at most $n$ commands as $n$-length strings over the alphabet $\{0,...,m-1\}$. This is equivalent to considering $n$ digit numbers in base $m$, or natural numbers from $0$ to $m^n-1$ where the number $k$ represents the program obtained from the base $m$ representation of $k$. $\endgroup$
    – Ariel
    Apr 1, 2021 at 10:57
  • 2
    $\begingroup$ @Ariel Write as an answer? $\endgroup$
    – Yuval Filmus
    Apr 1, 2021 at 13:34
  • $\begingroup$ Perhaps later, feel free! $\endgroup$
    – Ariel
    Apr 1, 2021 at 13:55

1 Answer 1

Reset to default
2
$\begingroup$

There is no need to assign a number. The program already is a number.

If you have $m$ opcodes and your program has $n$ instructions, then it can be interpreted as an $n$-"digit" number written in base $m$.

Improve this answer
$\endgroup$
4
  • $\begingroup$ How do I get access to the ordering such that inputting a given number returns the program that the number maps to? $\endgroup$
    – SubstantialRange
    Apr 1, 2021 at 22:07
  • $\begingroup$ @SubstantialRange, cs.stackexchange.com/q/10318/755 $\endgroup$
    – D.W. ♦
    Apr 1, 2021 at 22:09
  • $\begingroup$ @D.W. Wow, thanks for this! $\endgroup$
    – SubstantialRange
    Apr 1, 2021 at 23:05
  • 1
    $\begingroup$ @SubstantialRange: There is no mapping. The program is the number, the number is the program. $\endgroup$
    – Jörg W Mittag
    Apr 1, 2021 at 23:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.