# Questions tagged [turing-machines]

This tag is suited for questions involving Turing machines. Not to be confused with finite state machines and finite automata.

956 questions
Filter by
Sorted by
Tagged with
16 views

### In the Binary Domino problem, the size of the alphabet is 2 (i.e. each label on the sides of the dominos is either a or b). Is the BDOM decidable? [closed]

In the Binary Domino problem, BDOM, the size of the alphabet is 2 (i.e. each label on the sides of the square dominos is a single letter, either a or b). Is the BDOM decidable?
320 views

### Turingmachine for decision of mathematical conjecture

A consequence of the Halting-Problem is that there isn't a Turingmachine for the Entscheidungsproblem of Hilbert. An exersice I have to work on has the question: Does there exist a TM that prints 1 if ...
• 31
216 views

### Proving a corollary of Trakhtenbrot theorem

In Sets, Logic, Computation, Trakhtenbrot's theorem is stated as follows: Theorem 15.21 (Trakhtenbrot's Theorem). It is undecidable if an arbitrary sentence of first-order logic has a finite model (i....
• 579
67 views

### Turing recognizable, unrecognizable languages

What are examples of a a) language L such that both L and comp(L) are both unrecognizable b) decidable language D, and an unrecognizable language N, such that their union D ∪ N is decidable c) ...
17 views

### Let L = {1^s| such that there exist s consecutive 1s in the (decimal) expansion of π}. Is the language L Turing-decidable?

Let $L = \{1^s|$ such that there exist $s$ consecutive 1s in the (decimal) expansion of $\pi\}$. Is the language $L$ Turing-decidable? At first glance it seems like it would not be Turing-decidable ...
1 vote
55 views

### Understanding the proof of the uncomputability of the "productivity function"

I'm not following this proof of what Bools,Burgess,Jeffrey call the productivity function. The proof states that the value from the productivity function is not computable. They call it $s$, and it ...
• 1,025
11 views

### Is there some shared structure between Chaitin's constants of similar systems?

Since it is possible to approximate Chaitin's constant ($\Omega$) for some systems, is it known whether these numbers are somehow related to another when considering similarly operating Turing ...
• 150
89 views

### If A is decidable, is A* decidable?

my thought process is that since you can construct a Turing machine that decides the language, all you would need to do is construct it so that it continues to accept every time the same valid strings ...
• 89
51 views

### Deterministic Turing Machine for $L=\{ww : w\in \{0,1\}^{*}\}$ with restrictions.

I want to design a deterministc TM for the $L$ in the title, I've seen before for $$A=\{0,1,X,Y\} \hspace{0.5cm} B=\{0,1,\\}$$ $A$ is for the input alphabet and $B$ is for the tape alphabet. (...
44 views

### Number of Turing machines with $n$ states and an alphabet of size $c$ characters.

I want to count how many Turing machines there are with $n$ states (ignoring the rejecting and accepting states) and with an alphabet (input and working) of size $c$ characters. I have a solution, but ...
55 views

### Universal Turing Machines with Simple Encodings of Their Tape.

I am seeking a small $2$-symbol Universal Turing machine $U$ such that if $T$ is a Turing machine written to the tape of $U$ somehow, and I wish for $U$ to simulate $T$ with its tape initialized to $n$...
56 views

### Arithmetization of Turing machines

Refer to Turing's 1936 paper, page 248, last paragraph. I present the paragraph in verbatim below : The expression "there is a general process for determining..." has been used throughout ...
• 345
1 vote
98 views

### Why is a set is decidable iff it is the domain of a computable function

I'm studying three paradigms of computability theory: Godel's, Turing's, and von Neumann's. In the first two, it is given as a theorem that $f$ is a computable function iff its domain $S$ is decidable ...
• 3,344
1 vote
29 views

• 304
62 views

### Understanding Halting Problem, regarding the "input"

Before asking: My background is natural science and a bit of "coding" skills. I didn't study rigorous mathematics and logics since undergrad freshman, and this question is based on some ...
• 164
215 views

### Minimum Number of states for a Turing Machine

I am looking for a Turing Machine $M$ with $k$ states such that there is no other Turing Machine $M$' with fewer than $k$ states that recognizes the same language as $M$ (i.e., $L(M) = L(M')$). We ...
24 views

### Is the average number of steps of a $n$-state $k$-symbol Turing uncomputable?

There are finitely many $n$-state and $k$-symbol Turing machines. Call the number $N(n,k)= (2k(n + 1))^{kn}$ (according to Wikipedia https://en.wikipedia.org/wiki/Busy_beaver). Each of them either ...
1 vote
95 views

### Prove that NP ∩ co-NP closed under concatenation

I'm preparing for a test, and I've stumbled across the next question: "Prove that the complexity class NP ∩ co-NP is closed under concatenation." So my idea was that I know that a language \$...
• 11
182 views

### Axiomatization of reducibility notions

In computability theory, there are many notions of reducibility (such as Turing reducibility, enumeration reducibility, many-one reducibility, etc.). I am curious—has there been any attempt to ...
• 1,055