Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

One more thing - memory.

A Turing Machine is literally just a tape, a movable reader/writer, and a bunch of states that dictate what the reader/writer does.

As long as you have memory, the ability to write to memory, conditionals, and some form of looping, whether it's a `while` loop, a `for` loop, or a `jmp` or `GOTO` instruction, it's Turing complete.

Note that a conditional jump (`jne`, for example) satisfies both of the latter.



"Turing Complete" refers to a system which can be configured to be come any Turing Machine. When we write a particular program in some language and run it on some input, we have a Turing Machine. If the language lets us create any Turing Machine (i.e. do any Turing computation), then it is a Universal Turing Machine, and Turing Complete.

Turing's Tape Machine is a UTM because the tape can be initialized with contents to turn it into any TM. Any calculation for which there is a TM can be done by the UTM (if someone can figure out what to put on the tape).


yup memory. yup.

I forgot...


"Conditionals, loops, and memory" is an interesting list of requirements, because "memory" can be abstracted into anything. Functional Languages rely on the fact that the same code shall always produce the same outcome, and thus the "tape" has been changed into a series of concrete blocks. That said, I don't think anyone would argue that functional languages are not TC, but it is interesting to consider that the Tape becomes code in Lisp...




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: