Turing Machines

I've been playing around with interpreted machines quite a bit for genetic programming experiments. My current favorite minimal machine has 4 instructions:

0b00: Increment memory pointer (wraps)

0b01: Increment memory value (wraps)

0b10: Jump marker - Jump to next marker if memory value 1, prior if 2 (wraps)

0b11: Output current memory value

It has 2 tapes, instruction & memory. Memory is an array of byte.

This cannot handle any kind of input, but is useful for generating programs that can. Being able to pack 32 instructions into each interpreter machine word opens up some interesting possibilities for how we search the space.

Re: Turing Machines

#7

Post by samwho » Sat, Dec 21, 2024, 10:00 PM UTC

bob1029 wrote: post #6

I've been playing around with interpreted machines quite a bit for genetic programming experiments. My current favorite minimal machine has 4 instructions: 0b00: Increment memory pointer (wraps) 0b01: Increment memory value (wraps) 0b10: Jump marker - Jump to next marker if memory value 1, prior if 2 (wraps) 0b11: Output current memory value It has 2 tapes, instruction & memory. Memory is an array of byte. This canno…

I watched a fun talk in preparation for this post on unlimited register machines that you might enjoy: https://youtu.be/7Q-UwjgZ0q4?si=abEV1JKd9kuI8w8z

Re: Turing Machines

#8

Post by zokier » Sat, Dec 21, 2024, 10:01 PM UTC

I'd argue the key difference between Turing machines and real-world computers is that computers do IO, respond to events, have real-time characteristics, and are interactive. All of these are key features in making computers useful, but are poorly (if at all) captured by Turing machine model. It's one thing to compute something, and another thing to play Doom.

Re: Turing Machines

#9

Post by [deleted] » Sat, Dec 21, 2024, 10:21 PM UTC

samwho wrote: post #7

bob1029 wrote: post #6

I've been playing around with interpreted machines quite a bit for genetic programming experiments. My current favorite minimal machine has 4 instructions: 0b00: Increment memory pointer (wraps) 0b01: Increment memory value (wraps) 0b10: Jump marker - Jump to next marker if memory value 1, prior if 2 (wraps) 0b11: Output current memory value It has 2 tapes, instruction & memory. Memory is an array of byte. This canno…

I watched a fun talk in preparation for this post on unlimited register machines that you might enjoy: https://youtu.be/7Q-UwjgZ0q4?si=abEV1JKd9kuI8w8z

[deleted]

Re: Turing Machines

#10

Post by layer8 » Sat, Dec 21, 2024, 10:43 PM UTC

> By the end of this post, you will know:

> • What can and cannot be computed.

I don’t think it delivered on the “can” part. (And I don’t think we really know that well.)