11–20 of 38 posts
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…
> 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.)
What would you suggest I do to deliver on this?
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.
What’s different is that accessing an arbitrary position on the tape isn’t O(1), like normally assumed for memory, On the other hand, memory (and address space) on real-world computers is finite, so you can always find a large-enough constant to make the Turing equivalent O(1) again.
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…
What’s “marker” in the above?
> 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.)
When I was working on this post I found the way that Turing defined “computable numbers” I bit unsatisfying as well. What would you suggest I do to deliver on this?
Maybe rather:
• That some truths cannot be computed.
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.
It's a systolic array of Look Up Tables, 4 bits in, 4 bits out, with a latch on each latched.
Earlier quoted context omitted.
When I was working on this post I found the way that Turing defined “computable numbers” I bit unsatisfying as well. What would you suggest I do to deliver on this?
I would suggest to not promise it. ;) Maybe rather: • That some truths cannot be computed.
> Something is said to be "computable" if there exists an algorithm that can get from the given input to the expected output. For example, adding together 2 integers is computable.
I could probably have dug into some of the restrictions, like how it has to be a finite number of steps.
[1] https://ideas.lego.com/projects/10a3239f-4562-4d23-ba8e-f4fc...
I hope this LEGO Ideas Turing Machine gets turned into a released LEGO product [1]. It's not the first LEGO Turing Machine, but it is noteworthy because it is fully mechanical. [1] https://ideas.lego.com/projects/10a3239f-4562-4d23-ba8e-f4fc...
Earlier quoted context omitted.
I would suggest to not promise it. ;) Maybe rather: • That some truths cannot be computed.
I’m not sure I understand. I do explain what can be computed, don’t I? > Something is said to be "computable" if there exists an algorithm that can get from the given input to the expected output. For example, adding together 2 integers is computable. I could probably have dug into some of the restrictions, like how it has to be a finite number of steps.
At the level you’re describing Turing machines, it’s also not clear that readers would have a precise notion of what an algorithm is. At no point (unless I missed it) do you explain that any algorithm is supposed to be implementable as a Turing machine, or the assumption of what is otherwise known as the Church–Turing thesis.