# Questions tagged [turing-machines]

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

206 questions
Filter by
Sorted by
Tagged with
64 views

### Does busy beaver function of Riemann hypothesis imply it can be proved in a finite time? [closed]

I am not computer science background, just came across a paper https://www.scottaaronson.com/busybeaver.pdf We present a 5,372-state Turing machine that encodes Riemann’s hypothesis; in other words, ...
95 views

290 views

### Is coRE closed under concatenation?

I know that RE is closed under union, intersection, and concatenation (but not complement). It is likewise easy to show that coRE is closed under union and intersection (but not complement). What ...
131 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 ...
99 views

192 views

### Is the decidability of a language decidable? [closed]

Is there a Turing machine that takes a language as input and decides/semi-decides if it is a decidable language? Comments + answer say trivially the answer is yes; however, I'm wondering here would ...
474 views

186 views

### Minimal information needed for determine some function

From calculus, we know that if someone has a continuous function $f$, it is enough to know $f$'s values on the rationals in order to know $f$ on the entire line. In some sense, a "countable amount of ...
177 views

### Solving the Halting problem for most inputs [closed]

Is it possible to solve the following version of the Halting problem : given any Turing machine and some input tape, the program should answer if this pair halts or not except possibly for one Turing ...
589 views

### Are all turing machines paths predictable?

I was recently studying partial solutions to the halting problem and came across the problem which I discuss below. In particular I was studying when it was computable to tell if a turing machine has ...
42 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 ...
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.
390 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-...
511 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 ...
512 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 "...
313 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 ...
183 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 ...
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 ...
272 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 ...
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"...
263 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 ...