# Questions tagged [turing-machines]

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

219 questions
Filter by
Sorted by
Tagged with
1 vote
47 views

### Question About Turing Machine Computability [closed]

If p is a Turing machine then L(p) = {x | p(x) = yes}. Let A = {p | p is a Turing machine and L(p) is a finite set}. Is A computable? Justify your answer. So I'm trying to figure out how to solve ...
• 11
95 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.
606 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-...
• 1,046
695 views

### What is the practical importance of making or using a Turing complete language? [closed]

I get what a Turing machine is and what language is a Turing-complete language but when someone introduces me to a new programming language (like Solidity) and says it is Turing complete, what am I ...
• 19
902 views

### For a specific unbounded Turing machine, is its Halting problem undecidable?

The question is on the title. To make it clearer, I state some facts. We all know that the Halting problem with input is undecidable. It leads to, given a specific input (e.g. empty string), the ...
1k views

### How good can a halting detector be?

Is there a Turing Machine that can decide whether almost all other Turing Machines halt? Suppose we have some enumeration $\mathbb{N} \rightarrow \{M_i\}$ of Turing machines, and some notion of "...
1 vote
340 views

### What is the VC dimension of Turing machines with specified maximum size?

Note by "maximum size" in the question I'm referring to the size of the Turing machine's state machine. I chose Turing machines in the question to make the question concrete, but I'm also more ...
• 105
197 views

### Turing machines over a structure

I have heard of models of computation where you have a Turing machine, but instead of symbols over a finite alphabet you have elements from some tau-structure, and write instructions are replaced with ...
• 633
1k views

### Enumerating decidable languages

[The assumption in this question is wrong. It is possible to enumerate exactly the decidable languages with semideciders.] Lets say we have a TM $M_E$ enumerator that writes out codes of TM's on a ...
• 153
1 vote
523 views

### What is the time complexity of base conversion on a multi-tape Turing machine?

Base conversion is the problem of converting an integer between representations in two fixed bases. Without loss of generality consider the case of relatively prime bases. I think it's easier to ...
• 550
1k views

### Functions that are Not Efficiently Computable but Learnable

We know that (see, e.g., Theorems 1 and 3 of ), roughly speaking, under suitable conditions, functions that can be efficiently computed by Turing machine in polynomial time ("efficiently computable"...
• 812
294 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 ...
• 141
262 views

### Why bother with deterministic Turing machines when nondeterministic Turing machines consume less space and time? [closed]

I have a question on a part from the wikipedia page on Savitch's theorem: https://en.wikipedia.org/wiki/Savitch%27s_theorem The part in question is the following: [...], if a nondeterministic ...
• 275
222 views

### Is there any known strategy that avoids circuits and that respects believed separations to prove $P$ is not $NP$?

Vinay Deolalikar's approach tried to randomness is not strong enough, Blum's proof tried to show $P/poly$ is not strong enough, Mulmuley's and Smale's approach (while not enough to show $P\neq NP$) ...
• 12.6k
619 views

### Compressing information about the halting problem for oracle Turing machines

The halting problem is well-known to be uncomputable. However, it is possible to exponentially "compress" information about the halting problem, so that decompressing it is computable. More precisely,...
• 221
179 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) ...
• 642
1 vote
86 views

### Question on Turings Dissertation *Systems of Logic based on Ordinals*, Axiomatic Properties [closed]

I have a question on Alan Turing's Dissertation Systems of Logic Based on Ordinals, a scanned copy you can find here, or rewritten in LaTeX here, and also a copy of the published version here (but in ...
• 1,977
3k views

### Class of languages recognizable by single-tape 3-state TMs

I have for a while been curious about Turing Machines with exactly one tape and exactly 3 states (namely the start state $q_0$, the accept state $q_{accept}$, and the reject state $q_{reject}$). Note ...
• 2,758
496 views

The time hierarchy theorem states that turing machines can solve more problems if they have (enough) more time. Does it hold in some way if the space is limited asymptotically? How does $\textrm{DTISP}... • 59 9 votes 0 answers 369 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-... • 199 1 vote 0 answers 187 views ### An alternative model of a probabilistic Turing machine [closed] A probabilistic Turing machine operates with an additional tape of random bits, and its output is a random variable with some distribution over the random bits. Is it also useful to talk about the ... • 111 2 votes 0 answers 89 views ### Is there a DCSL that cannot be recognized in O(n^2) steps by a deterministic LBA? Is there a context sensitive language$L$so that$L$cannot be recognized by a deterministic linear bounded turing machine in$O(n^2)$steps, but still can be recognized by a deterministic LBA? The ... • 59 1 vote 0 answers 104 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 ... 1 vote 1 answer 570 views ### A question of relationships between #P and PSPACE [closed] Let us assume there is some machine X that converts boolean formula to following form in polynomial time:$$\Phi(x_1, x_2 .. x_m) = r_1(x_{i_1}, x_{j_1}, x_{k_1}) \land r_2(x_{i_2}, x_{j_2}, x_{k_2}) ... • 207 1 vote 2 answers 2k views ### Is iszero of the untyped lambda calculus sound and complete? [closed] I am using the following definitions in the notation of Haskell. In case it matters, I would like to use only the$\alpha,\beta,\eta$reductions rather than the Haskell evaluation rules. ... • 173 0 votes 1 answer 164 views ### Enumerator for the language w#w^R? [closed] I'm trying to build a Turing machine diagram for the language w#w^R, where w^R is the reverse of w, and w is a word made up of 0's and 1's. I'm trying to think of an algorithm but I can't think of ... • 19 2 votes 1 answer 92 views ### Characterisation of computability of partial functions from infinite words into finite words by functions with prefix-free domain The following is taken from K. Weihrauch, Computable Analysis, page 21. The notation$f : \subseteq A \to B$means a partial function. By$\Sigma^{\omega}$and$\Sigma^{\ast}$we denote the set of ... • 1,977 2 votes 5 answers 426 views ### A definition of computable numbers that requires to "wait an infinite amount of time" to get the correct result; how to make this precise Consider the following definition: A number$x \in \mathbb R$is computable, if there exists a (one-tape) Turing machine which (running infinitely long) writes the binary expansion of$x$onto its ... • 1,977 19 votes 3 answers 2k views ### "The" category of Turing machines? Disclaimer: I know very little about complexity theory. I'm sorry but there is really no way to ask this question without being (terribly) concise: What should be the morphisms in "the" category ... • 301 15 votes 2 answers 473 views ### (How) Could we discover/analyze NP problems in the absence of the Turing model of computation? From a purely abstract math/computational reasoning point of view, (how) could one even discover or reason about problems like 3-SAT, Subset Sum, Traveling Salesman etc.,? Would we be even able to ... • 5,225 4 votes 0 answers 107 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 ... • 331 7 votes 3 answers 584 views ### Where does the modern canonical version of the Turing machine come from? Turing's original 1936 description of his a-machine differs in several respects from the Turing machine I studied at university, leading me to questions: The Turing machine I learned about was ... 0 votes 0 answers 157 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 ... • 331 -1 votes 1 answer 547 views ### Where can I find a Turing machine evaluating arithmetic expressions? [closed] Is there a Turing machine that can evaluate arithmetic operations with brackets containing +, -, and ... • 109 -2 votes 1 answer 126 views ### Are there any known problems that require potential nontermination to solve? [closed] Apart from problems that specifically have to do with Turing machines, like "Simulate a Turing Machine with the given description", are there any problems that require Turing-complete potentially ... • 131 0 votes 1 answer 198 views ### A metric space on Turing machines Let$L$be a decidable language. Let$X^L$be the set of deterministic Turing machines which decide$L$. Define two machines$A,B\in X^L$to be time-equivalent if$t_A(w) = t_B(w)$for all$w \in \... 651 views

### Understanding between lambda-calculus and other abstract machines (like Turing machine and Markov algorithm)

If we look on abstract machines we could noticed analogue with modern computers (of course). What I mean? I mean this points: 1. Model of implementer (In Turing machine it is description of head, ...
• 25
557 views

### Can all mathematical operations be encoded with a Turing Complete language? [closed]

In High School Computing I was taught the Structured Program Theorem - that you could implement any mathematical operation using: Sequence Selection Iteration After completing a Computer Science ...
• 2,541
248 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 ...
3k 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 ...
• 3,703
934 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 ...
16k 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 ...
• 617
169 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? ...
• 3,035
630 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 ...
• 131
1 vote
1k 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" ...
• 121
215 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 ...
• 455
185 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 ...
• 269
310 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.
• 119
2k 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 ...
• 5,025 