41–50 of 109 posts
Basically, anything that can recurse is Turing-complete.
[1] https://en.wikipedia.org/wiki/Primitive_recursive_function
It's not turing complete until someone writes a ray tracer in it!
http://funarg.nfshost.com/r2/code/sed/ray/ray.sed
Earlier quoted context omitted.
Practically realizable CPU’s are just deterministic finite state automata with a very large number of states.
Sure, but their states aren't quite what you'd consider to be states for an abstract Turing machine. There's a CPU state that also happens to set some pixels on a display to a certain value, for example.
Earlier quoted context omitted.
I think the other formalism you're talking about is https://en.wikipedia.org/wiki/Markov_algorithm There are a number of different models of universal computation that were formulated in the 1930s or soon afterward and can all be proven to be equivalent in power. In CS courses in the U.S., people might learn about more than one of these and also prove that they're equivalent. But only the one with the tape and symbol…
You are right. In Romania we also prove that different computational models are equivalent (Turing machine, lambda calculus, Markov machine, logic programming)
Is there a text which guides how to write such a proof?
Earlier quoted context omitted.
Sure, but their states aren't quite what you'd consider to be states for an abstract Turing machine. There's a CPU state that also happens to set some pixels on a display to a certain value, for example.
So a display is simply a device you plug into some pins on the computer to format the computer’s state in a more human-friendly way. You could do the exact same thing with a Turing machine.
Earlier quoted context omitted.
You are right. In Romania we also prove that different computational models are equivalent (Turing machine, lambda calculus, Markov machine, logic programming)
>prove that different computational models are equivalent (Turing machine, lambda calculus, Markov machine, logic programming) Is there a text which guides how to write such a proof?
Has anyone written a kind of Turing machine gateway API, where people write an adaptor to the API and you can then use the gateway to use any Turing machine backend to run any other(Turing complete) program. Would be interesting to see e.g. how fast Microsoft Word runs on a sed based backend.
This that you describe is essentially a Universal Turing Machine.
Earlier quoted context omitted.
Turing machines are finite state automatas with random read and write access to a tape (i.e. memory). One turing machine can write to a certain position on a tape, while another turing machine can read from that position on the tape. At that point we communicated between two turing machines. Add some electric engineering to allow this tape position to send electrical signals from one place to another other a wire and…
No, because the two Turing machines run in different contexts, one of which is unable to access a graphical display.
Digital displays only get bytes as input and output visible light for humans. These bytes are mostly an arbitrary format optimized for performance. Sed can output arbitrary bytes too based on an input program. That's what "sed is turing complete" tells us.
Earlier quoted context omitted.
CPUs are not simple Turing machines; they produce side effects as a result of their computation and interact with peripheral devices.
Turing machines are finite state automatas with random read and write access to a tape (i.e. memory). One turing machine can write to a certain position on a tape, while another turing machine can read from that position on the tape. At that point we communicated between two turing machines. Add some electric engineering to allow this tape position to send electrical signals from one place to another other a wire and…