# Tagged Questions

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

91 views

### Characterisation of P in terms of register machines

It is a well-known result that Turing machines and random access machines (RAMs) can simulate each other with a polynomial slowdown. It is relatively straightforward to prove that indirect addressing ...
2k views

### Turing Machine restrictions that render halting decidable

If one restricts Turing Machines to a finite tape (i.e., to use bounded space $S$), then the halting problem is decidable, essentially because after a number of steps (which can be calculated from the ...
107 views

### Halting problem for finite tape TM [closed]

If we have a primitive CPU/computer with small amount of registers and/or RAM, it is easy to check if the program will loop endlessly: just write down all registers/RAM cells states at each state and ...
12k views

### Real computers have only a finite number of states, so what is the relevance of Turing machines to real computers?

Real computers have limited memory and only a finite number of states. So they are essentially finite automata. Why do theoretical computer scientists use the Turing machines (and other equivalent ...
41 views

### What is the simplest universal unidimensional interaction net system?

The Interaction Combinators are possibly the simplest multidimensional system of interaction nets that is Turing-complete. What about interaction nets with only 2 ports - 1 principal, 1 auxiliary? ...
74 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 ...
86 views

### Multi Head universal Turing machine

It is common knowledge that a universal Turing machine can simulate any Turing machine with logarithmic overhead. Is it possible to make this overhead constant by constructing an analogous "Universal" ...
117 views

### Do bounded-visit nondeterministic linear bounded automata recognize only regular languages?

Do bounded-visit nondeterministic linear bounded automata recognize only regular languages? By a nondeterministic linear bounded automaton (nLBA) I mean a single-tape nondeterministic Turing machine ...
141 views

### Does Wikipedia assume a solution to the halting problem in their description of universal one way functions?

(As for the question in the title: the answer must be no, but then I don't understand what is intended.) The Wikipedia page on one way functions states: Goldreich gives one construction of a ...
145 views

### Are there any open problems concerning decidability? [duplicate]

I am learning computability theory. I am just interested to know some famous problems (Formally languages) whose decidability is in question.
66 views

### How Turing machines compare with process calculi w.r.t. expressivity? [duplicate]

Some time ago there were heated debates, and some researches argued, that so-called interactive computations (understood as "computations=calculations+communication"), like Pi-calculus, actors model, ...
35 views

### Maximum entropy definition of universal distribution

Kolmogorov complexity and the "universal distribution" $m$, defined e.g. here and discussed in detail in the book of Li and Vitanyi, are defined with respect to a universal Turing machine (UTM). ...
347 views

### Is there a non-deterministic linear time algorithm for CNF-SAT?

The decision problem CNF-SAT can be described as follows: Input: A boolean formula $\phi$ in conjunctive normal form. Question: Does there exist a variable assignment that satisfies $\phi$? I'm ...
306 views

### Fastest Turing Machine

Recently I have been reading about Kolmogorov Complexity. As such I started thinking about the "fastest turing machine". In particular I am not interested in finding such a machine, I am only ...
239 views

### Is there a theory of computation that takes failure and decay of the computation substrate into account?

There are obvious differences between a Turing machine and a real computer. Not only is the latter finite in size, it is also prone to failures and it is made from decaying matter. The kind of ...
152 views

### Computing the DAG of a program given source code or AST

I've seen many papers on scheduling components or tasks once a DAG for the program is known, either by user-input or by domain restriction (i.e. all cross shaped 5-pt stencil codes have a known DAG). ...
199 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 ...
88 views

### Space time lower bound with $\mathsf{PSPACE}$ oracle

Does a single tape Turing machine with access to $\mathsf{PSPACE}$ oracle needs more than $\mathsf O(1)$ working tape memory and $\mathsf O(1)$ working time to solve $\mathsf{NP}$-complete problem? ...
48 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 ...
136 views

### Is Redis Turing Complete?

Is Redis with all its data types (Strings, Lists, Hashes, Sets, Sorted Sets, etc.) Turing Complete?
56 views

### Is multiprocessing possible on a Turing Machine? [closed]

I recently created a parallel implementation of the Merge Sort, in which the sorting of several groups was accomplished by different processes, and was wondering if this was theoretically possible on ...
97 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 ...
119 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 ...
995 views

### What functions can System F not compute?

In this wikipedia article on Turing Completeness it states that: The untyped lambda calculus is Turing complete, but many typed lambda calculi, including System F, are not. The value of typed ...
277 views

### Was bombe machine turing complete?

In the recent movie called The Imitation Game, there is a affirmation that Turing was building his theoretical machine. That machine is the Bombe Machine. Is this machine really equivalent to a Turing ...
111 views

### Simple example of halting-unprovable Turing machine

Is there a simple example of a Turing machine $M$, such that whether $M$ halts or not on the empty input cannot be proved within the current mathematical system? Specifically, I'm curious whether ...
60 views

### Is there an easy way to improve this Tree Normal Form for Busy Beaver candidates?

In "Attacking the busy beaver 5" by Heiner Marxen and Jürgen Buntrock, an algorithm to create tree normal candidates is explained (it also contains a concise introduction of the relevant terms). If ...
123 views

### What are different definitions of Universal Turing-machine?

I am not sure what is the appropriate way for this, but I would like to collect different possible definitions/variants of Universal Turing-machines. Here are the ones I know, post below if you know ...
412 views

### Looking for Literature Source for Following idea

I am quite certain that I am not the first to entertain the idea that I am going to present. However, it would be helpful if I can find any literature related to the idea. The idea is to construct a ...
99 views

### Busy beaver candidate elimination: Minimum space requirements

I'm currently enrolled in a course that introduces Turing machines. As I wanted to play around a bit, I wrote a little TM engine and had it search for busy beavers (it successfully found the 4-state 2-...
131 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 ...
78 views

### Conflicting definitions regarding TM and Recursively Enumerable languages

In Lewis's and Papadimitriou's book "Elements of the Theory of Computation" the transition table is a function $\delta: Q \setminus F \times \Gamma \rightarrow Q \times (\Gamma \cup \{L,R\})$. However,...
238 views

### Source of Turing-machine illustration

I am writing a computer science textbook and want to use an illustration showing a Turing machine. Images are all over web, but almost always without authorship/illustratorship credited. I need to ...
188 views

### Does hyper-computational power of infinite time Turing machines also require infinite memory?

Can a infinite time Turing machine perform hyper-computation like checking the consistency of the set theory ZF without using infinite memory?
1k views

### A total language that only a Turing complete language can interpret

Any language which is not Turing complete can not write an interpreter for it self. I have no clue where I read that but I have seen it used a number of times. It seems like this gives rise to a kind ...
67 views

190 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 ...
171 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 ...
1k views

### Computing input length on a one-tape Turing machine

In connection with this question it occurred to me to wonder: what is the time complexity for a single-tape single-head Turing machine to compute the length of its input? To be specific, let's say ...