Add another test, and some notes, to the tests.
Chris Pressey
5 months ago
| 379 | 379 | | >/ |
| 380 | 380 | | >)----(/)<<< |
| 381 | 381 | = State{ tape=(... [7] 0 0 5 ...), stack=(... [0] ...), halt=True } |
| 382 | ||
| 383 | Notes | |
| 384 | ----- | |
| 385 | ||
| 386 | Ultimately, we would want to use this conditional construction in a translation from | |
| 387 | Turing machines to Burro programs, as part of a Turing-completeness proof. | |
| 388 | ||
| 389 | The construction above can be used to rewrite the value on the tape at one spot. | |
| 390 | But to do so, it needs several "scratch cells" adjacent to the tape cell - one for | |
| 391 | each conditional test. With a defined tape encoding, this is not difficult. However, | |
| 392 | the contents of these cells does matter. We leave the original value being tested in | |
| 393 | the rightmost one, for example. We will need to clean up after ourselves and ensure | |
| 394 | that we have fresh scratch cells for the next go 'round. | |
| 395 | ||
| 396 | I think that's as straightforward as subtracting the original test value from the | |
| 397 | final value of the "current cell" before we move off of it. | |
| 398 | ||
| 399 | | +++++ | |
| 400 | | ( | |
| 401 | | +++++++++ | |
| 402 | | >/ | |
| 403 | | >)(/) | |
| 404 | | --( | |
| 405 | | < | |
| 406 | | --------- | |
| 407 | | +++++++++++++ | |
| 408 | | > | |
| 409 | | >/ | |
| 410 | | >)--(/) | |
| 411 | | ----( | |
| 412 | | << | |
| 413 | | ------------- | |
| 414 | | +++++++ | |
| 415 | | >> | |
| 416 | | >/ | |
| 417 | | >)----(/)-----<<< | |
| 418 | = State{ tape=(... [7] ...), stack=(... [0] ...), halt=True } | |
| 419 | ||
| 420 | Multiple instances of this value-rewriting construction must also appear. This is | |
| 421 | because the rules for rewriting a tape cell are different in every state. We need | |
| 422 | to be able to select which value-rewriting construction to use. | |
| 423 | ||
| 424 | We don't see why we can't re-use the principle we've already established, to create | |
| 425 | this selector construction. As we noted, if we have a sequence of greater-than | |
| 426 | comparisons, we account for the overlapping execution of multiple blocks by having | |
| 427 | each block undo the previous block (if any): | |
| 428 | ||
| 429 | if stateId > 0: | |
| 430 | a | |
| 431 | endif | |
| 432 | if stateId > 2: | |
| 433 | a′ b | |
| 434 | endif | |
| 435 | if stateId > 4: | |
| 436 | b′ c | |
| 437 | endif | |
| 438 | ||
| 439 | The main complication here is that to obtain the inverses here, we must do a lot more than | |
| 440 | just swap `+`'s and `-`'s. The construction that we want to invert, is itself a large | |
| 441 | structure of multiple conditionals. However, that is no problem in principle, because | |
| 442 | every Burro program has an inverse, which can be obtained in a straightforward manner. | |
| 443 | ||
| 444 | I should write an example here, but it would be beneficial to have it be machine-generated. |