# Questions tagged [turing-machines]

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

625 questions
21 views

### is there a linear bounded automaton the decides $A_{nfa}$?

first post here :) I was wondering, since regular languages are context sensitive, and since linear bounded automatons can act as an acceptors for context sensitive language, is it possible or is ...
32 views

### Diagonal argument applied to computable numbers

Upon applying the Cantor diagonal argument to the enumerated list of all computable numbers, we produce a number not in it, but seems to be computable too, and that seems paradoxical. For clarity, ...
76 views

### What does it mean for a number to be independent of ZFC?

Since the definition of the Busy Beaver function by Radó in 1962, an interesting open question has been what [is] the smallest value of $n$ for which $BB(n)$ is independent of ZFC set theory. Source: ...
7 views

### Prove the languages |L<M>| = 2 and |L<M>| $\not=$ 2 to be non-Turing recognizable or non-recursively enumerable

I am trying to prove the non-recursively enumerable property of two languages. L = {$\langle M \rangle$: |L$\langle M \rangle$| = 2}. and L = {$\langle M \rangle$, |L$\langle M \rangle$| $\not=$ 2}. ...
13 views

### How to prove {e: L($M_e$} is decidable} is not Turing-recognizable?

I have reduced {e:$M_e$ accepts e} to this one. But I failed to reduce in the other direction. And I don't know if there is an algorithm to solve this. Thank @Noah Schweber who tells me it's not ...
20 views

### L = {$(n,w)$ $w$ is a binary representation of the n-th fibbonacci number} membership decision problem

I am a student currently studying Computational Models. I still don't have a full understanding of the subject and was wondering about languages of the form $L = \left \{(n,w) | f(n) = w \right \}$ ...
47 views

### Difference of two decidable languages?

I've been learning about TMs in class lately and we talked about the decidability of two languages by union or intersection. I was wondering if you have two decidable languages, L1 and L2, is their ...
79 views

### Complexity of a copy and reverse Turing Machine

I have a turing machine, that appends a reversed copy of a string to the end of the string. The alphabet of the TM is {a, b}. Copy & Reverse TM How can I prove the time complexity of this Turing ...
14 views

### Turing Machines recognizing the same language

Is it possible for two turing machines that take different types of inputs, for example $\langle M,w\rangle$ and $\langle M\rangle$, to recognize the same language?
59 views

### What rule allows to determine the symbol on an $i$-th cell of the tape of an Infinite Time Turing Machine at any limit stage?

Assuming that $s$ denotes a particular symbol that can appear on the tape, $\alpha$ denotes any limit ordinal such that $\alpha \ge \omega$ and $C_i[\tau]$ denotes the symbol on the $i$-th cell of ...
49 views

### Can we enumerate finite sequences which have no halting continuation?

Note: this is a cross-post from CS.SE, since I haven't gotten an answer there. I am trying to deepen my understanding of the relationship between the Halting Problem and Godel's Completeness Theorem (...
19 views

11 views

### Reference for type-2 Turing machines and does the limit lemma hold?

I am looking for a good reference on the theory of type-2 Turing machines (infinite input tape, finite output tape say). In particular, whether the Shoenfield Limit Lemma holds in this case and ...