On algorithmic equivalence of instruction sequences for computing bit string functions
| Authors | |
|---|---|
| Publication date | 06-04-2014 |
| Number of pages | 27 |
| Publisher | Ithaca, NY: ArXiv |
| Organisations |
|
| Abstract | Every partial function from bit strings of a given length to bit strings of a possibly different given length can be computed by a finite instruction sequence that contains only instructions to set and get the content of Boolean registers, forward jump instructions, and a termination instruction. We look for an equivalence relation on instruction sequences of this kind that captures to a reasonable degree the intuitive notion that two instruction sequences express the same algorithm. |
| Document type | Working paper |
| Note | Version 2 |
| Language | English |
| Published at | http://arxiv.org/abs/1402.4950v2 |
| Downloads |
1402.4950v2
(Submitted manuscript)
|
| Permalink to this page | |
