6 ms·
The Power of One-State Turing Machines (2018)
- javajosh 7y agoOkay I'll volunteer to be the dummy who says I don't get it. The cell of a Turing tape can contain an arbitrary number? The head of Turing machine can add?? I think my underlying assumptions have been violated, which means either I have something interesting to learn or this is a bad result. Probably the former.
- mitchtbaum 7y agoINPUT: can? "contain an arbitrary..." & ifnot= "something interesting to learn" OUTPUT: https://en.m.wikipedia.org/wiki/Arbitrariness#See_also https://en.m.wikipedia.org/wiki/Arbitrariness#See_also #~~ (trying to scratch together code you can run that'll answer your question.. hm, the initial function is untyped without a better sense of 'number'.)
- kd5bjo 7y agoIn the Turing machine formalism that was taught at my university(1), the set of symbols that can be stored in a cell must be finite, but can otherwise be anything needed to solve the problem at hand. For each state in the associated state machine, there’s effectively a lookup table that maps the current tape symbol to some other, and an instruction about how to move the tape head for the next step. This means, in particular, that you can annotate symbols on the tape by having different variants of each input symbol, so long as the number of variants is strictly bounded. (1) There are many equally-powerful variants, so there’s no guarantee that others will be working with the same definition.
- fhars 7y agoThe tape cannot contain arbitrary numbers, but symbols from any finite alphabet, which can be int256_t, and the transition function can be any partial function on pairs of tape symbols and input states.
- Sharlin 7y agoNot arbitrary. Modulo some constant k, the size of the tape alphabet. They're just choosing as the tape alphabet the set { 1, 2, …, k-1 }, and as the transition function one that maps each n to n+1 mod k. It's just a lookup table.
- daveFNbuck 7y agoThe transition function can only do modular addition within a cell, but the paper also describes how to build a k-ary counter. If your single state has the increment lookup table for a single cell, you just need to move to the next cell to do carries, and move to the previous cell to leave the counter when you're done. A special carry character is written instead of zero to make sure you leave the whole counter, and you convert it to zeroes as you leave.
- progval 7y agoThere are many ways to define Turing Machines: * only binary alphabet, or allow any finite alphabet on the tape(s) * tape is infinite in a single direction or in both (and various possibilities as to how to handle reaching the edge) * there is one tape or there are more * the head has to move every time, or can it remain on the same cell * etc. And they are all equivalent in terms of computability (ie. they can compute the same functions), and mostly equivalent in terms of algorithmic complexity (ie. they take the same time to run, up to a polynomial). So almost no one bothers actually saying which model they use, unless they are doing a rigorous proof. However, when papers like this one say "Hey, let's take my favorite model of Turing Machines and restrict it so that [X]", then the results highly depends on what their favorite model is. Except they don't always bother saying which one it is. For example, if you restrict yourself to Turing Machines with a single state, two tapes, and any alphabet allowed on at least one of the tapes, then it's enough to emulate any one-tape Turing machine, simply by writing the state on a single cell of the second tape and repeatedly read it. Which in turn are known to be able to emulate any conventional model of Turing Machines.
- daveFNbuck 7y agoLooking at the first page of the linked PDF, it's not explicit about whether the alphabet must be finite, although it's implied by the summary saying that addition can only be done modulo some finite value. It is explicit about having an arbitrary alphabet, a single tape that's infinite in both directions and that the head has to move every time. I don't think I've ever seen anyone restrict a Turing machine in a novel way and not follow that up with a rigorous proof.
- beaker52 7y agoI've never understood what the fascination with Turing machines is or what they actually are.
- goto11 7y agoIt is the simplest possible computer which can actually be built.
- mitchtbaum 7y agoThey don't look so simple tonight.
- TuringTest 7y agoThat should make you think about the complexity of all other possible computers
- fnrslvr 7y agoYou're reading a paper that analyzes the capabilities of a particular highly-constrained subclass of Turing machines. Actual research findings aren't necessarily going to be simple just because the model of computation being studied is simple. (Although a similar investigation into the capabilities of, e.g., a similarly constrained subset of Python, would probably tend to be a whole lot more lengthy and arduous.) The parent's point is that the Turing machine model of computation admits a very concise definition -- roughly a page depending on brevity and formatting. An industrially viable programming language or hardware architecture typically requires a standard spanning hundreds of pages to define.
- bspammer 7y agoThere are plenty of visualizers out there to help out e.g. http://turingmachine.io/ http://turingmachine.io/ The simplest way I can describe them without any maths is that at any point in time they have two inputs, and three outputs. The inputs: * The current "state" of the machine, which is usually shown as a letter - there are a finite number of states the machine can be in, but this number can be as big as you like. * The value currently being pointed at on the tape. The possible values are again finite, but can be as big as you like. The outputs: * A new value to write on the tape. * A new state to be in. * Whether to shift the tape left or right. If you choose your mappings from inputs to outputs carefully, this machine can solve literally every problem your desktop computer can solve. I'd call that pretty amazing.
- todd8 7y ago## Computability Turning Machines are a simple, purely hypothetical, machines that have allowed computer scientists/mathematicians to conclude very profound properties of computation. Although they are mentioned with some frequency here, it's not a subject that most of us have any training in. I had the good fortune to study computer science while in college many years ago. There was a lot less to learn back then and I was introduced to the theory of computation at the undergraduate level. For those that haven't had the pleasure of problem sets covering Turing Machines but would like to learn something about them, I recommend the Stanford Encyclopedia of Philosophy entry on Turing machines [1]. It goes into more depth than Wikipedia while being very easy to understand. Turing machines are extraordinarily simple, much simpler than any real computer. The fact that Turing Machines deserve an entry in a Philosophy reference is because of their power in elucidating the very nature of computation. About 80+ years ago, it was discovered that the set of problems that can be solved/computed by a Turing Machine is exactly the same set that can be solved with the Church's Lambda Calculus, [2] and recursive functions as formalized by Gödel's [3]. This, to me surprising, result led to the Church-Turing thesis: the hypothesis that any effectively computable (i.e. solvable through some mechanistic procedure) can be solved by a Turning Machine. From this we know, for example, that true algorithms don't exist for a whole host of problems. This isn't the same claim that some problems are hard and don't have tractable exact solutions (e.g. the knapsack problem or the traveling salesman problem [4]); there are algorithms for these problems--they simply take a very long time. Some interesting problems on the other hand have no algorithm at all. This can be shown by demonstrating that no Turing Machine could be constructed to solve the problem (e.g. the halting problem [5]). What about quantum computers? They look like an approach so different and so powerful that maybe they will provide a stronger model of computation than that limited by the bounds of Church-Turing. Unfortunately, the qubit based approaches that we are now pursuing have been demonstrated to be "equivalent" to classical (Turing) machines, just with different performance time/space tradeoffs. So qubit based quantum computers may someday solve challenging, exponential time problems, but they won't solve every problem. ## Turing machines Turing's insight was that any mechanical procedure for computation could be modeled by a simple machine, the Turing Machine. A Turing Machine has a "tape", think of it as an infinite strip of paper divided into cells, like an infinite array: tape[k]. Each cell can hold a symbol from some finite alphabet. There is a single read/write head positioned at a location on the tape. The head can read a symbol from the location or erase/write a symbol the location, and then it can move one location left or right. Turing machines also have a state from some finite range of states, say 1...N. One state is designated as the initial state. Finally, there is a state transition table in the Turing Machine that determines its operation. For each combination of (1) current state and (2) current symbol under the read/write head, the transition table gives (a) the new internal state and (b) the symbol that should be written on the tape at the current location and (c) the direction the head should move--left or right. When I first saw the definition of a Turing Machine, I thought that it looked unlike a computer. The state table seemed to encode the entire operation of the machine. It could potentially be a huge table of specific operations to solve some problem. Turing machines seemed to me to be special purpose constructions unlike the more flexible architectures of programmable computers. Indeed, we studied a number of different Turing Machines that would solve simple problems with inputs from the tape. The big surprise for me was seeing a Universal Turing Machine. It turns out that there are Turing Machines, having a fixed reasonably small state transition table that can do anything that any other Turing Machine can do. These "Universal" machines use a program on the tape that provides the instructions to process the remaining input data from the tape. The idea of a Turing Machine doesn't rely on lots of states, a few is enough to construct a universal machine. Likewise, there are Universal machines that need a tape that extends in only one direction and tape vocabularies that have a very limited number of symbols. [1] https://plato.stanford.edu/entries/turing-machine/ https://plato.stanford.edu/entries/turing-machine/ [2] https://plato.stanford.edu/entries/lambda-calculus/ https://plato.stanford.edu/entries/lambda-calculus/ [3] https://plato.stanford.edu/entries/recursive-functions/ https://plato.stanford.edu/entries/recursive-functions/ [4] https://en.wikipedia.org/wiki/Travelling_salesman_problem https://en.wikipedia.org/wiki/Travelling_salesman_problem [5] https://en.wikipedia.org/wiki/Halting_problem https://en.wikipedia.org/wiki/Halting_problem