# Questions tagged [turing-machines]

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

37 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
0answers
332 views

### Is there a Turing complete planetary system?

Seemingly simple things have turned out to be capable of computation - Conway's Game of Life, Wolfram's Rule 110, etc. Has anyone devised a Turing complete system using suns, planets, moons, sub-...
0answers
147 views

### What can you do with a moving knife besides cutting a cake?

In the fair cake-cutting, two different computational models are used: A discrete model, in which the algorithm issues queries to the players and proceeds according to their replies; A continuous ...
0answers
245 views

### Data structures lower bounds on Turing machines

Have there been any results on lower bounds for implementing data structures on Turing machines, e.g. stacks, queues, etc ? I guess that people are mostly interested in models with random access, but ...
0answers
132 views

### Small universal monotone Turing machines

This paper surveys small universal Turing machines. What are some examples of small universal monotone Turing machines, as described by Schmidhuber? Which of these are efficient (polynomial time) ...
0answers
2k views

### What would a PDA be with a queue instead of a stack?

A while ago it occurred to me that the stack data model in a push-down automaton could be exchanged for a queue or deque model. I've explored this a bit as a pet project and it looks like an automaton ...
0answers
164 views

### What is the Kolmogorov complexity of arithmetic?

Chaitin's incompleteness theorem says no sufficiently strong theory of arithmetic can prove $K(n) > L$ where $K(n)$ is the Kolmogorov complexity of the number $n$ and $L$ is a sufficiently large ...
0answers
316 views

### Regular languages in lambda calculus

With Turing machines, by imposing certain restrictions on the form of the transition function, one can get a machine that accepts only regular languages. I am wondering what is the counterpart in ...
0answers
177 views

### The size of output in circuit complexity

In circuit complexity we have one circuit for each input size. The size of the output is determined solely by the size of the input. So it seems to me that taken in its strict sense there are ...
0answers
291 views

### Does Depth-First-Search admit a quasilinear time algorithm in mutitape Turing Machine model?

Depth-First-Search (DFS) has a quasilinear (i.e.,$\widetilde{O}(m+n)$) time algorithm in random access model (RAM). I am curious about whether DFS still admits a $\widetilde{O}(m+n)$ time algorithm in ...
0answers
351 views

### Games on Turing machines that are AH-hard

I'm interested in proving that finding optimal play in a particular two-player game is harder than the arithmetic hierarchy. I suspect this to be true, because even carrying out a deterministic end-...
0answers
83 views

### Libraries for programming automata and Turing machines

What are the most useful libraries around for coding related to automata and Turing machines? By useful I mean the number of functions and algorithms supported by it.
0answers
260 views

### How fast can we sort a list if we know how it was written?

Let $G$ be a linear time (deterministic) turing machine that takes positive integers $n$ in unary to lists of length $n.$ For any fixed such $G$, define sparse-sort(G,n) as the problem of sorting the ...
0answers
101 views

### Why primitive rotation is $53.13^\circ$ in the quantum Turing machine used by Vitanyi for Quantum Kolmogrov Complexity?

Right now I am going through Quantum Kolmogorov Complexity Based on Classical Descriptions by Vitanyi. In the introduction, the author assumed the primitive rotation $\theta = 53.13^\circ$ to have ...
0answers
155 views

### How is Cooks overlap argument applied in Vitányi's theorem?

In P.M.B. Vitányi, Relativized Obliviousness, MFCS'80 paper one can read that the proof of Theorem 1 is based on the overlap-argument of Cook, however I don't see how this argument is applied. The ...
0answers
411 views

0answers
73 views

0answers
177 views

### Is it possible to simulate a Linear Bounded Automata with logic circuits where links have min-max bounded delays? I need a reference in the literature

Consider the following building blocks, which can be used to construct a logic circuit: basic logic gates {OR, AND, NOT} which have $n$ input and $m$ output pins, with $n,m\ge 1$. generators of ...
0answers
198 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 ...
1answer
597 views

### Langton's ant questions

I'm a mathematician currently working on the Langton's ant conjecture, just for fun. I have some result but I don't know if they are meaningless. So that is why I'm asking. 1) Is there a mathematical ...
0answers
105 views

### Functional abbreviation for Inst expression in Turing's 1936 paper

In Turing's 1936 paper "On Computable Numbers", For a Turing Machine $M$, $Inst(q_i S_j S_k L q_l )$ means that if $M$ scans symbol $S_j$ under $m-configuration$ $q_i$, then the symbol ...
0answers
69 views

### Given a program specification, S, what can be said about the size and efficiency of programs that exactly satsify S, with respect to the size of S?

Suppose we are given a program specification, $S$, and we want to reason about programs $P$ that satisfy $S$. One might like to think that if the specification is 'simple', the the program should be '...
0answers
61 views

### Asymptotic time required to simulate a Turing machine M for k steps

Problem: Given an encoding of a Turing machine M and a natural number k as input, find the output of M (given a blank tape) after k steps. Wikipedia's page on EXPTIME-complete says it takes O(k) time ...
0answers
102 views

### Convenient forms of Turing machines

Let us suppose that I have defined a new convenient form of the Turing machine for processing of some specific sort of commonly used structures. This form of TM contains some specific features ...
0answers
66 views

### Analogues of different complexity classes in various models

We suspect following relation: $$TC^0\subsetneq NC^1\subsetneq L\subsetneq NL\subsetneq AC^1\subsetneq NC^2\subsetneq P\subsetneq NP\subsetneq PH\subsetneq PSPACE$$ in Turing/boolean circuit ...
0answers
120 views

### Is BigInteger-based Brainfuck Turing Complete?

All of the proofs of Turing-Completeness I've found for Brainfuck rely on its cells being fixed-width integers that wrap around upon over/underflow. The "parent language" P'' on which ...
0answers
111 views

### Can you diagnolize without mentioning simulation?

Are there any known diagonalization proofs, of a language not being in some complexity class, which do not explicitly mention simulation? The standard diagnolization argument goes: here is a list of ...
0answers
154 views

### Questions about the definition of the Quantum Turing Machine

I am trying to have a better understanding of the definition of the Quantum Turing Machine. My questions: If the output of a quantum program is the eigenvalue of the ground state of a Hamiltonian ...
0answers
195 views

### How to picture Non-Deterministic Turing machine seeking out boolean expression to satisfy examples

Traditionally, the boolean satisfiability problem is framed as, given a boolean formula, is there an assignment that satisfies the formula. I'm trying to look at this differently - from the ...
1answer
161 views

### Where is the proof of universality of Rule110 in Stephen Wolfram's book?

I have Stephen Wolfram's book A New Kind Of Science. And I want to find the proof of the universality of Rule 110. I couldn't find the clue in the contents page since it only shows 12 chapters and no ...