4 ms·

A Simulator of a Universal Turing Machine (2017)

23 points by gone35 5y ago

unwind 5y ago
I love it how it claims to be "in C++", yet I had to read a lot of the snippets to find anything that wasn't just C. Finally realized it uses default argument values in some functions, but that was all I could find in the time I wanted to spend. Not a fault per se I guess, but I wonder why people do things like that. To me it'd be like using an aircraft carrier to go shopping, or something. And yes, I realize there's no real cost in requiring a C++ compiler but ignoring 99% (or whatever) of the language's capabilities, but it looks weird to me. :)
- zokier 5y ago
  It's targeting VS2010, which iirc had really crappy C compiler and far better C++ compiler. That's why writing pure C in MSVC/Windows world is relatively rare compared to C masquerading as C++.
- doodpants 5y ago
  It also uses "//" for comments.
  - misnome 5y ago
    Ah, but that is in C99!
- marcosdumay 5y ago
  It would be like using an aircraft carrier to go shopping if the carrier had the same driving difficulty or a car, required the same crew, could use the same parking space and roads, had the same fuel efficiency but was still pretty much a giant capable war machine. Oh, and if it costed the same too. I guess on this scenario a lot of people would take their carriers to shopping too.
dane-pgp 5y ago
(2017) I was hoping it might include a compiler that converts code from a higher level language into the language of the Turing Machine, but sadly that doesn't seem to be the case. That means the example programs are all hand written, though, which is quite impressive.
- davidweichiang 5y ago
  ELVM (https://github.com/shinh/elvm https://github.com/shinh/elvm) is a C compiler with a Turing machine backend.
tromp 5y ago
The author only shows the description of the 29-state universal Turing machine LCCP_UTM as an input to itself in the console screen picture, which is rather illegible. It is the 1787 character string y000000x00000x00001x0x0000000000001x0000010000011x00000y00000y1x00000h00000h1x00001x00001x0x00001000001a0x00001100001c0x00001y00010y1x00010x01010x1x00010a0001101x00010c0010011x00011x00101x1x00011a00011a1x00011c00011c1x00011y11100y1x00100x00110x1x00100a00100a1x00100c00100c1x00100y11100y1x00101x00101x1x00101000111a0x00101101000c1x00101a00101a1x00101c00101c1x00110x00110x1x00110001000a1x00110100111c0x00110a00110a1x00110c00110c1x00111x00111x0x0011100001001x0011110001011x00111a00111a0x00111c00111c0x01000x01001x0x01000001000a1x01000101000c1x01001x01001x0x01001001001a0x01001101001c0x01001a01001a0x01001c01001c0x01001y00010y1x01010x01010x1x01010001011a0x01010101100c0x01010a01010a1x01010c01010c1x01011x01011x0x0101100101100x0101110101110x01011a01011a0x01011c01011c0x01011y01101y1x01100x01100x0x0110000110000x0110010110010x01100a01100a0x01100c01100c0x01100y01110y1x01101x10000x0x01101001111a1x01101101111a1x01101a01101a1x01101c01101c1x01110x10001x0x01110001111c1x01110101111c1x01110a01110a1x01110c01110c1x01111x01010x1x0111100111101x0111110111111x1000001000000x1000011000010x10000a10000a0x10000c10000c0x10000y10000y0x10000h10010a1x1000101000100x1000111000110x10001a10001a0x10001c10001c0x10001y10001y0x10001h10010c1x10010x10011x1x1001001001001x1001011001011x10010a1001001x10010c1001011x10010y10010y1x10011x10011x1x1001101010000x1001111010010x10011a1001101x10011c1001111x10011y10100y0x10100x10100x0x1010001010000x1010011010010x10100y10101y1x10101x10110x0x1010101010101x1010111010111x10110010111s0x10110111000s0x1011101011100x1011111011110x10111a1100100x10111c1100101x10111y10111y0x1100001100000x1100011100010x11000a1100110x11000c1100111x11000y11000y0x11001011010h1x11001111011h1x1101001101001x1101011101011x11010y11010y1x11010s0000101x1101101101101x1101111101111x11011y11011y1x11011s0000111y0 Considering it's over a size 8 alphabet, that amounts to 5361 bits (over 26 times longer than a self interpreter for a simple functional machine model https://tromp.github.io/cl/cl.html https://tromp.github.io/cl/cl.html) Minsky is more famous for his 7 state 4 symbol universal Turing machine, whose universality is far less direct as it simulates a tag system. I wonder how big a tag system that machine translates to, when trying to feed it to itself.
- imode 5y ago
  Regarding the "functional machine" model, that's not a machine model, and the steps to evaluate that interpreter don't constitute an effective method.
zoba 5y ago
If you like this, consider joining the Turing Machine’s subreddit I moderate: https://www.reddit.com/r/turingmachines/ https://www.reddit.com/r/turingmachines/ There, you’ll find several Turing Machine simulators including at least one that runs online: http://morphett.info/turing/turing.html http://morphett.info/turing/turing.html
- deknos 5y ago
  is there also a subreddit for programming/hacking/zip quines?

23 points by gone35 5y ago

I love it how it claims to be "in C++", yet I had to read a lot of the snippets to find anything that wasn't just C. Finally realized it uses default argument values in some functions, but that was all I could find in the time I wanted to spend. Not a fault per se I guess, but I wonder why people do things like that. To me it'd be like using an aircraft carrier to go shopping, or something. And yes, I realize there's no real cost in requiring a C++ compiler but ignoring 99% (or whatever) of the language's capabilities, but it looks weird to me. :)

zokier 5y ago
It's targeting VS2010, which iirc had really crappy C compiler and far better C++ compiler. That's why writing pure C in MSVC/Windows world is relatively rare compared to C masquerading as C++.
doodpants 5y ago
It also uses "//" for comments.
- misnome 5y ago
  Ah, but that is in C99!
marcosdumay 5y ago
It would be like using an aircraft carrier to go shopping if the carrier had the same driving difficulty or a car, required the same crew, could use the same parking space and roads, had the same fuel efficiency but was still pretty much a giant capable war machine. Oh, and if it costed the same too. I guess on this scenario a lot of people would take their carriers to shopping too.

dane-pgp 5y ago

(2017) I was hoping it might include a compiler that converts code from a higher level language into the language of the Turing Machine, but sadly that doesn't seem to be the case. That means the example programs are all hand written, though, which is quite impressive.

davidweichiang 5y ago
ELVM (https://github.com/shinh/elvm https://github.com/shinh/elvm) is a C compiler with a Turing machine backend.

tromp 5y ago

The author only shows the description of the 29-state universal Turing machine LCCP_UTM as an input to itself in the console screen picture, which is rather illegible. It is the 1787 character string y000000x00000x00001x0x0000000000001x0000010000011x00000y00000y1x00000h00000h1x00001x00001x0x00001000001a0x00001100001c0x00001y00010y1x00010x01010x1x00010a0001101x00010c0010011x00011x00101x1x00011a00011a1x00011c00011c1x00011y11100y1x00100x00110x1x00100a00100a1x00100c00100c1x00100y11100y1x00101x00101x1x00101000111a0x00101101000c1x00101a00101a1x00101c00101c1x00110x00110x1x00110001000a1x00110100111c0x00110a00110a1x00110c00110c1x00111x00111x0x0011100001001x0011110001011x00111a00111a0x00111c00111c0x01000x01001x0x01000001000a1x01000101000c1x01001x01001x0x01001001001a0x01001101001c0x01001a01001a0x01001c01001c0x01001y00010y1x01010x01010x1x01010001011a0x01010101100c0x01010a01010a1x01010c01010c1x01011x01011x0x0101100101100x0101110101110x01011a01011a0x01011c01011c0x01011y01101y1x01100x01100x0x0110000110000x0110010110010x01100a01100a0x01100c01100c0x01100y01110y1x01101x10000x0x01101001111a1x01101101111a1x01101a01101a1x01101c01101c1x01110x10001x0x01110001111c1x01110101111c1x01110a01110a1x01110c01110c1x01111x01010x1x0111100111101x0111110111111x1000001000000x1000011000010x10000a10000a0x10000c10000c0x10000y10000y0x10000h10010a1x1000101000100x1000111000110x10001a10001a0x10001c10001c0x10001y10001y0x10001h10010c1x10010x10011x1x1001001001001x1001011001011x10010a1001001x10010c1001011x10010y10010y1x10011x10011x1x1001101010000x1001111010010x10011a1001101x10011c1001111x10011y10100y0x10100x10100x0x1010001010000x1010011010010x10100y10101y1x10101x10110x0x1010101010101x1010111010111x10110010111s0x10110111000s0x1011101011100x1011111011110x10111a1100100x10111c1100101x10111y10111y0x1100001100000x1100011100010x11000a1100110x11000c1100111x11000y11000y0x11001011010h1x11001111011h1x1101001101001x1101011101011x11010y11010y1x11010s0000101x1101101101101x1101111101111x11011y11011y1x11011s0000111y0 Considering it's over a size 8 alphabet, that amounts to 5361 bits (over 26 times longer than a self interpreter for a simple functional machine model https://tromp.github.io/cl/cl.html https://tromp.github.io/cl/cl.html) Minsky is more famous for his 7 state 4 symbol universal Turing machine, whose universality is far less direct as it simulates a tag system. I wonder how big a tag system that machine translates to, when trying to feed it to itself.

imode 5y ago
Regarding the "functional machine" model, that's not a machine model, and the steps to evaluate that interpreter don't constitute an effective method.

zoba 5y ago

If you like this, consider joining the Turing Machine’s subreddit I moderate: https://www.reddit.com/r/turingmachines/ https://www.reddit.com/r/turingmachines/ There, you’ll find several Turing Machine simulators including at least one that runs online: http://morphett.info/turing/turing.html http://morphett.info/turing/turing.html

deknos 5y ago
is there also a subreddit for programming/hacking/zip quines?