# Questions tagged [turing-machines]

The Turing machine is a fundamental model of computation, especially in theoretical work.

187 questions
Filter by
Sorted by
Tagged with
1k views

### Is there a name for “physical things out of which one can build a Turing machine”?

One of the amazing things about computer science is that the physical implementation is in some sense "irrelevant". People have successfully built computers out of several different substrates -- ...
387 views

### Busy Beavers: quadratic relation of output size and running time?

When glancing at the running times and output sizes of some Busy Beaver candidates on this page, I find that there seems to be a rough (up to some small power of 10) quadratic relation between output ...
590 views

### Another weird $O(N \log{N})$ Turing machine

This is another question related to the (still open) nice question "Alphabet of single-tape Turing machine" by Emanuele Viola. I describe the question very informally (perhaps it has a trivial ...
365 views

### Is there any research on Turing machines with transition relation homomorphic to given algebraic structure?

A Turing machine is defined as a structure $TM(L,Q,T)$, where $L,Q$ are sets of symbols and internal states of TM respectively, and T is a transition relation: $T: L \times Q \to L \times Q$ for ...
195 views

### Turing Machine which generates order on the set of its states

The Turing machine (TM) is an abstract model for effective implementation of (finite algorithmic) calculation. TM is defined over some alphabet of symbols L and reading data performs a finite sequence ...
275 views

20k views

### Relationship between Turing Machine and Lambda calculus?

Is there a relationship between the Turing Machine and the Lambda calculus - or did they just happen to arise about the same time?
624 views

### Circuits with oracles vs. Turing Machines with oracles

Put simply: what is the correspondance between Turing machines with oracles, and uniform circuit families with oracles? How are the latter defined in order to obtain the same computational model, for ...