The 2024 Developer Survey results are live! See the results

# Questions tagged [turing-machines]

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

244 questions
Filter by
Sorted by
Tagged with
1 vote
68 views

### Smallest 2-symbols Turing machine that can decide primality using unary encoding

I am interested in Turing machines that can decide primality using only two symbols and, hence, unary encoding for the input. Currently I have a solution that has 29 useful states (not counting the ...
1 vote
108 views

### Are Turing Machines Models?

I am wondering whether it is correct to say that Turing machines are models of, say, the lambda calculus, in the model theoretical sense. Lambda calculus and Turing machines are equivalent ...
127 views

### Can a RAM machine with polynomial memory be simulated by a multi-tape Turing machine without extra time or space costs?

It is known that many-tape Turing machines can be simulated by a one tape Turing machine with extra runtime costs. Furthermore, a single-tape Turing machine with a larger alphabet can be simulated by ...
103 views

### Smoothed analysis in the Turing machine model

Smoothed analysis is usually defined using real numbers: given $n$ and $\sigma$, the smoothed runtime of an algorithm is the maximum, over all inputs of size $n$, of the runtime on the input when it ...
• 2,294
1 vote
188 views

### Inconsistent Turing machine

I am reading responses to the Lucas-Penrose argument and many make sense to me. Some of them employ inconsistent Turing machines as a model of mind to escape Gödel’s first incompleteness theorem (as ...
• 151
1 vote
91 views

### Planar Turing Machine with (relatively) Small Alphabet

There is a simple construction that takes any drawing of a Turing Machine in the plane and outputs another planar, equivalent one with a "small" blowup in the number of states, and only two ...
1 vote
111 views

### Turing 1936 Skeleton Tables Procedure

I am reading Turing 1936 to learn about the halting problem from its origin. However, I encountered a roadblock upon reaching section four, in which Turing demonstrates that his m-configuration tables ...
87 views

### Complexity of chess with 50-move rule

It is known that evaluating who wins in $n \times n$ chess positions is EXP-complete (and thus unconditionally not in P), and this effect is due to the game having rich possibilities for exponentially ...
252 views

249 views

### Complexity of determining whether the language of an P machine is empty

Suppose you are given a deterministic Turing machine and you are guaranteed it runs in polynomial time. What's the computational complexity of determining whether the language accepted by the machine ...
• 1,049
164 views

### Self-universality and Turing-completeness

By definition, any formal system (machine, language, etc.) that can compute (simulate) any Turing machine or its equivalent (lambda calculus, recursive functions, etc.) is Turing complete. I wonder if ...
• 151
538 views

### Technical limitations of Turing machines due to the input and output encoding of values

Convention: Since I will be asking about some technicalities around Turing machines, it behooves to give a precise definition: say, here, “Turing machine” will stand for a $2$-symbol $1$-tape machine ...
• 841
132 views

### "Interesting" problems in $NLogTime \cap coNLogTime$

In terms of machine model, I'm interested in multitape Turing machines with random access to the input via a query tape. Criteria for "interesting" in this context: Not in $DLogTime$: "...
• 1,214
1 vote
174 views

### Decidability of the complexity of decision problems

This might be a question that is related to some of the existent questions on the topic in the title, but I still find some answers either not full, or the topic still slightly different (maybe due to ...
• 111
74 views

### Resource bounded Kolmogorov complexity hardness on average over a non uniform distribution of inputs

$K^{poly}$, as well as other related problems such as $MCSP$, is believed to be hard on average [1, 2] when the input is sampled from a uniform distribution (since otherwise one way functions, pseudo-...
• 187
284 views

• 13.1k
229 views

### Understanding the construction of an uncomputable function

The following is from Arora and Barak's "Computational Complexity." I think one does not have to read the second paragraph of the proof to answer this question. Theorem 1.10 There exists a ...
• 109
410 views

### Does the Linz Ĥ applied to ⟨Ĥ⟩ correctly transition to its final reject state? [closed]

Everyone knows that it is impossible for a TM halt decider to derive the correct halt status for any input that does the opposite of whatever value it derives. When we take the conventional ideas of: (...
• 43
124 views

• 1
960 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 ...
• 10.6k
180 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 ...
• 119
112 views

### Halting behavior of a randomly selected Turing machine?

Let $TM(k,2)$ be the set of Turing machines with $k$-states and $2$ symbols. Let $h(k)$ be the number of machines in $TM(k,2)$ that halt when run on the blank input. Is \$\lim_{k \to \infty} \frac{h(k)...
• 251
377 views

### Is there a concept of "Lego complete"? If not, does it make sense to develop one?

We know the concept of Turing Completeness. These days when I play lego with my kids. I realised that Lego is kinda like programming language: we can build a lot of things with a fairly small set of ...
• 171