Turing Machine Implementation in Assembly -- 4
Budget: $30 – $250 USD
See this project:
https://github.com/FrankBuss/turingmachine
It implements a register machine with vm.py. An example program is test.asm. You can run it like this:
python3 vm.py test.asm
To filter out bots, post the output of this program, any application without it will be ignored. The architecture of the VM is pretty simple: at the first 3 bytes is an address pointer, an A register, and a X register is saved. The program then starts at the next byte, which is address 0 regarding the address pointer. Instructions are documented in vm.py. It halts when it encounters a halt instruction.
Your task is now to write a Turing machine to simulate this register machine. I started it with machines/vm.json. You can run the Turing machine with this command:
cargo run -- machines/vm.json
Also show the current final tape as a test. The initial tape encodes the test2.asm program.
The idea of the Turing machine is that the program is encoded on the initial tape, including the address pointer, A and X register at the start, with - as a delimiter. The Python script generates such an output. The program starts at the first "p" marker instead of a space.
The "loada" instruction is already implemented. I used some kind of microcode concept, where the current microcode step is encoded at the beginning of the tape. This allows to reuse parts of the transition table, as you can see at the end of the currently other implemented instruction "output", where the p marker is moved, which is also done for "loada".
As a test to check that you can do it, implement the "a2x" command, see "todo" in the json file, which could be similar to the copy block at the end, and should be possible to do in a short time. If it runs correctly, then the final tape should have a 00101010 at the 3rd byte for the X register. You send me the extended json file for it.
If you accept this job, you have to finish the Turing machine so that it can simulate all instructions of the VM. You also have to write an assembler program, which tests all instructions, and creates a string output, which shows that the instructions are correct as a self test (you have to fix the vm.py program, if there are problems with the original implementation, but should be fine). Then you copy the encoded initial tape output to the json file, and it has to produce the same "Outputs as ASCII" output string, and the final tape must also have the same registers and memory content as the VM. The tape output of the test.asm has to work as well. You can send me the final solution as a PR to my github repository.
The memory read and write instructions might be a bit tricky. As you can see in the Python program, the pointer register is set to 0 after executing the instruction. This is because I thought to implement it like this: first the plus marker is placed at the beginning of the RAM (without the registers). Then the pointer value is checked. And if not 0, then the plus marker is moved forward, and the pointer value is decremented. If it is 0, then the marked byte is copied. I already started it with the copy block, which technically for the loada instruction doesn't need the + marker, because it can use the p marker, but this can be probably reused then for the read instruction, and the write instruction would be the same in reverse. And the unused "start" block shows a sample how to implement the read instruction, with the pointer decrement, p move, and then the byte move. You can use this part, or write your own, and then delete this part.
What would be cool is to implement a faster RAM read and write implementation than O(n^2). It should be possible to implement it in O(n), by extending the tape: between each RAM byte, an extra address word is stored. Then when moving the + marker, it doesn't need to go back to the counter for each step, but can just copy the address to the next address space, and then decrement it. This should make it faster for bigger RAMs. But this also requires a new tape generation in vm.py and is not required for this job.
This should be a pretty simple project and probably needs less than a day for a good programmer with some experience in writing Turing machines, so should be possible to do it for like $100. Maybe sometime I write a scientific paper about it, and I can add you as a co-author for it, if you like.
https://github.com/FrankBuss/turingmachine
It implements a register machine with vm.py. An example program is test.asm. You can run it like this:
python3 vm.py test.asm
To filter out bots, post the output of this program, any application without it will be ignored. The architecture of the VM is pretty simple: at the first 3 bytes is an address pointer, an A register, and a X register is saved. The program then starts at the next byte, which is address 0 regarding the address pointer. Instructions are documented in vm.py. It halts when it encounters a halt instruction.
Your task is now to write a Turing machine to simulate this register machine. I started it with machines/vm.json. You can run the Turing machine with this command:
cargo run -- machines/vm.json
Also show the current final tape as a test. The initial tape encodes the test2.asm program.
The idea of the Turing machine is that the program is encoded on the initial tape, including the address pointer, A and X register at the start, with - as a delimiter. The Python script generates such an output. The program starts at the first "p" marker instead of a space.
The "loada" instruction is already implemented. I used some kind of microcode concept, where the current microcode step is encoded at the beginning of the tape. This allows to reuse parts of the transition table, as you can see at the end of the currently other implemented instruction "output", where the p marker is moved, which is also done for "loada".
As a test to check that you can do it, implement the "a2x" command, see "todo" in the json file, which could be similar to the copy block at the end, and should be possible to do in a short time. If it runs correctly, then the final tape should have a 00101010 at the 3rd byte for the X register. You send me the extended json file for it.
If you accept this job, you have to finish the Turing machine so that it can simulate all instructions of the VM. You also have to write an assembler program, which tests all instructions, and creates a string output, which shows that the instructions are correct as a self test (you have to fix the vm.py program, if there are problems with the original implementation, but should be fine). Then you copy the encoded initial tape output to the json file, and it has to produce the same "Outputs as ASCII" output string, and the final tape must also have the same registers and memory content as the VM. The tape output of the test.asm has to work as well. You can send me the final solution as a PR to my github repository.
The memory read and write instructions might be a bit tricky. As you can see in the Python program, the pointer register is set to 0 after executing the instruction. This is because I thought to implement it like this: first the plus marker is placed at the beginning of the RAM (without the registers). Then the pointer value is checked. And if not 0, then the plus marker is moved forward, and the pointer value is decremented. If it is 0, then the marked byte is copied. I already started it with the copy block, which technically for the loada instruction doesn't need the + marker, because it can use the p marker, but this can be probably reused then for the read instruction, and the write instruction would be the same in reverse. And the unused "start" block shows a sample how to implement the read instruction, with the pointer decrement, p move, and then the byte move. You can use this part, or write your own, and then delete this part.
What would be cool is to implement a faster RAM read and write implementation than O(n^2). It should be possible to implement it in O(n), by extending the tape: between each RAM byte, an extra address word is stored. Then when moving the + marker, it doesn't need to go back to the counter for each step, but can just copy the address to the next address space, and then decrement it. This should make it faster for bigger RAMs. But this also requires a new tape generation in vm.py and is not required for this job.
This should be a pretty simple project and probably needs less than a day for a good programmer with some experience in writing Turing machines, so should be possible to do it for like $100. Maybe sometime I write a scientific paper about it, and I can add you as a co-author for it, if you like.