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

learn more… | top users | synonyms

1
vote
3answers
69 views

How does one generally use partial function in logical statements?

How does one generally use partial function in logical statements? How it's done in practice? Specifically, let $M$ by a Turing machine, $f_M:\{0,1\}^*\to\{0,1\}$ the characteristic function which ...
2
votes
1answer
49 views

Are all constrtuctively describable functions continuous? Do they necessarily come with a topology?

In the paper "An injection from $\mathbb{N}^\mathbb{N}$ to $\mathbb{N}$" by @AndrejBauer, about the question whether there exists an injection $\mathbb{N}^\mathbb{N}\to\mathbb{N}$, we writes ...
2
votes
0answers
73 views

Prove that $\overline{L}$ is not recognizable by showing that $B_{TM} \le_m L$

$\textbf{Problem}:$ $L$ = $\{\langle M \rangle$ | $M$ is a Turing machine over $\{0, 1\}$ such that for some $x \in \{0,1\}^*$, $M$ does not halt on input $x\}$. $B_{TM}$ = $\{ \langle M \rangle$ | ...
0
votes
2answers
68 views

Turing machine true/false questions

There is a non-regular language that is recognized by a Turing Machine. I believe the answer to this is true, because Turing machines can "count" computations and ...
1
vote
1answer
66 views

Let $L_{UIUC}$ = $\{ \langle M \rangle$ : $L(M)$ contains the string $UIUC\}$. Prove that $L_{UIUC}$ is undecidable.

Been stumped as to why the following proof works. Note: I have taken this proof directly from here. Proof by reduction from $A_{TM}$. Suppose that $L_{UIUC}$ were decidable and let $R$ be a Turing ...
0
votes
1answer
67 views

What does it mean for a Turing machine $M$ to accept $\epsilon$

Suppose $B_{TM}$ = $\{ \langle M \rangle$ | $M$ is a Turing machine over $\{0, 1\}$ and $M$ accepts $\epsilon\}$. I do not understand what it means for $M$ to accept $\epsilon$. Can someone explain ...
3
votes
0answers
115 views

Proving a language is not recognizable

I have the following question that I just want to verify I have done correctly. Let $L$, $L_1$, $L_2$ $\subseteq \Sigma^*$ such that $L = L_1 \cup L_2$, and $L_2$ is decidable. Prove that if $L$ is ...
0
votes
0answers
234 views

A turing machine for binary addition

How would I write a turing machine which has configurations which does 2 bit binary addition?
1
vote
2answers
65 views

The halting problem for tapes that are or are not completely blank

Is it possible to construct a Turing machine that halts only if the tape is not completely blank? Also, is it possible to construct one to halt if the tape is completely blank? Intuitively, I think ...
2
votes
1answer
74 views

Designing a turing machine

Suppose you have a tape that has a block of $a$ strokes followed by a space, followed by a block of $b$ strokes, followed by a space, followed by a block of $c$ strokes, and otherwise blank. ...
1
vote
1answer
86 views

If $L_1 \cap L_2$ is decidable, prove/disprove that $L_1$ and/or $L_2$ are decidable

Question: Let $L_1$ and $L_2$ be languages over the alphabet $\Sigma$. If $L_1 \cap L_2$ is decidable, then $L_1$ is decidable or $L_2$ is decidable (or they both are). Definition of a decidable ...
1
vote
1answer
23 views

Interpreting probabilistic time turning machines

I was trying to understand better the definition of a strong PSRG and I came across this expression which I am trying to understand better: $$ Pr_{r \in \{0,1\}^l}[A(r) = "yes"]$$ Where r is a truly ...
1
vote
1answer
123 views

Number of possible configurations in a Turing Machine

While studying for an up-and-coming exam, I stumbled upon the following question: $$ L=\{\langle M \rangle,\langle w\rangle:M\text{ is single-tape and }M \text{ running on }w \text{ doesn't go over ...
1
vote
1answer
34 views

Languages in P that are not P-complete

Why aren't there any languages in P that are not P-complete?
2
votes
1answer
59 views

Prove that RE is closed under reduction

Prove that the class RE is closed under reduction. Definitions: A language $ A \subseteq \Sigma^*$ is called reducible to $ B \subseteq \Gamma^*$ ( denoted by $A \leq B$) if there is a computable ...
1
vote
1answer
37 views

Languages that are not comparable in $R$

I want to know if there are $2$ languages $A,B\in{R}$ such that there's no reduction between them. Namely, $2$ languages $A$ and $B$ $\in$ $R$ such that $A\not\le B$ and $B\not\le A$ Thanks a lot!
1
vote
1answer
163 views

prove Turing recognizable

This is actually an old exam question its not my homework; Let L = { : M is a TM with an input alphabet of {a,b} and M accepts at most one word, i.e. M either accepts no words or accepts exactly one ...
1
vote
0answers
44 views

Extended PDA vs TM

We studied in class that PDA is less powerful than TM. My question is: Extended PDA : for every $\alpha,\beta \in \Gamma \cup \{\epsilon\}$, $\sigma \in \Sigma \cup \{\epsilon\}$, $q,r \in Q$, $w ...
0
votes
0answers
21 views

reverse of language, decidability

Consider a language L(D) = {w: w and its reverse are in L(D)}. Does reverse of L(D) is the same language ? If so, then consider L = {: M is a DFA for L(D)}, does this make this a turing decidable ...
2
votes
1answer
48 views

Given a single taped deterministic turing machine what's the least amount of calculations needed in order to receive the language

Given a single taped deterministic turing machine what's the least amount of calculations needed in order to receive the language $L_k=${$0,1$}$^*0${$0,1$}$^{k-1}$. My intuition says that i'll need ...
1
vote
1answer
74 views

Solving the halting problem for *almost* all machines?

As I understand it, the proof of the halting problem’s undecidability is conceptually pretty simple. You postulate a machine $h(m, x)$ which (1) always halts and (2) returns 1 if $m$ halts with input ...
2
votes
1answer
45 views

Concrete universal turing machine

I read about universal turing machines in the internet, but I did not find a concrete listing of a universal turing machine and a descreption, how a specific turing machine has to be coded that the ...
1
vote
0answers
88 views

Oracle Turing machine - $E_{\text{TM}}$ and $PCP$.

$$E_{\text{TM}}=\{\langle M\rangle|M\text{ is a TM and $L(M)=\emptyset$}\}.$$ $E_{\text{TM}}$ is undecidable $$PCP=\{\langle P\rangle|P\text{ is an instance of the Post Correspondence Problem with a ...
2
votes
1answer
46 views

Reducing A$_\text{TM}$ to REGULAR$_\text{TM}$

We can solve A$_\text{TM}$ problem using REGULAR$_\text{TM}$. Assume $R$ is a Turing machine that decides REGULAR$_\text{TM}$. We construct $S$ to decide A$_\text{TM}$ as follows On input ...
0
votes
1answer
44 views

Assign Integer to Each Turing Machine

I have the following problem: suppose that we have an infinite set of symbols, $A = \{a_1, a_2, ...\}$ from which all Turing Machine input alphabets are chosen. Show how we could assign an integer to ...
2
votes
0answers
61 views

Blanks in the Tape of a Turing Machine

I used to have a lot of trouble with Turing Machines, primarily because I thought that in-between input symbols on the tape, one could have an arbitrary number of blanks, so every input would need to ...
2
votes
1answer
91 views

Turing Machine for comparing, copying, and operating

If one wants to design a Turing Machine for a function such as this: Where $x>0,y>0$ and are both integers represented in unary, so an example movement in this TM on the read-write head would ...
2
votes
1answer
215 views

Show that the language TOT={<M> | M is a Turing Machine that halts with all inputs} is not recursively enumerable nor its complement.

I've been thinking about how to show this but I'm stuck. I'm required to prove this: "Show that the language TOT={#M# | M is a Turing Machine that halts with all inputs} is not recursively ...
0
votes
1answer
43 views

Computably enumerable and partial functions

I've been tasked with proving, formally or informally, that these conditions of a language A which is a subset of {0,1}* are equivalent statements. I must first show that A itself is computably ...
1
vote
0answers
64 views

Primitive recursive and Turing machines

Can someone give me a hint or the start of a possible proof for the following theorem: A function $f: \mathbb{N}^r \rightarrow \mathbb{N}$ is primitive recursive if and only if there is a ...
1
vote
0answers
35 views

(2,5) Turing Machine implemented with chess pieces

I recently came across a (limited) reference to a (2,5) Turing machine implementation that can be represented using chess pieces on a 2D board. I know it is possible to implement a UTM using ...
2
votes
1answer
37 views

Undecidability of REGULAR_TM

In case you have Sipser's Introduction to the Theory of Computation 3rd edition, I am asking specifically about the proof of theorem 5.3, how the language REGULAR_TM is undecidable. \begin{equation} ...
1
vote
0answers
11 views

Is the language that consists of machine configurations whose language is a subset of even palindromes semi-decidable?

Let $PAL = \{ww^R\ | w\in\{0,1\}^*\}$. Then let $A = \{\langle M\rangle \ | \textit{M is a Turing Machine and } L(M)\subseteq PAL\}$ Is A semi-decidable (Turing recognizable or recursively ...
0
votes
1answer
31 views

Constant value function Turing machine.

How would one go about writing a Turing machine which always computes to a certain value? If the value is small, the problem is trivial of course, but how could I write a Turing machine for the ...
0
votes
1answer
45 views

Turing machines and tape complexity

Are the following statements true and/or false? There is a total function $g: \mathbb{N} \rightarrow \mathbb{N}$ so that for each Turing machine $M$ and each natural number $t$ we have: (*) ...
0
votes
1answer
77 views

Recursively enumerable language of Turing machines

If you have the language $L_{h}=\{M_{i} | (\exists z \in \sum ^{*}) M_{i}\text{ halts on some input } z\}$ where $M_{i}$ are Turing machines, is $L_{h}$ recursively enumerable? I'm fairly certain ...
0
votes
0answers
49 views

Overwriting a blank symbol is semi-decidable

Consider the following language: $$ L = \left\{ \langle M \rangle~ \middle| \begin{array}{c} M \text{ is a single-tape TM that writes a blank symbol $\sqcup$ over a nonblank} \\ \text{symbol during ...
0
votes
0answers
27 views

Is a sum of an elementary chain on low models low?

We have an elementary chain of low models $(\mathcal{A}_i)_{i\in\omega}$ such that for every $n\in\omega$ the model $\mathcal{A}_{i+1}$ is a model obtained by Low Basis Theorem from the set $A_i$ that ...
1
vote
1answer
35 views

Is recursive join of a sequence of low sets also low?

A set $A$ is low when $\deg(A)'\leq 0'$. Suppose we have a sequence of low sets $(A_i)_{i\in\omega}$ such that for every $n\in\omega$ we have $$\deg(\bigoplus_{i<n}A_i)'\leq 0'$$ Let ...
1
vote
0answers
56 views

Time constructible, non-time constructible functions

A function T:N→N is time constructible if T(n)≥n and there is a Turing Machine M that computes the function x↦└T(|x|)┘ in time T(n). (└T(|x|)┘ denotes the binary representation of the number ...
0
votes
0answers
37 views

Proving DIAG2 = $\{\langle M\rangle | \langle M\rangle\langle M\rangle\notin{L(M)}\}$ is not semi-decidable!

This is a homework problem so I don't expect a full solution. I just want a hint on how to do this problem. Just in case you are not familiar with the notation, $\langle{M}\rangle$, means a string ...
1
vote
1answer
67 views

How do you argue (or prove) that a certain Turing machine accepts a language?

I have an existing Turing machine that is essentially the same as this one here: X is the blank symbol, # is the end of the tape. The format is input/output, direction. 0 indicates failure ...
5
votes
1answer
113 views

Lower bounds for bb(7) and bb(8) wanted

The busy beaver function $bb(n)$ is not known for $n \geq 5$. Does Anyone know suitable lower bounds for $bb(7)$ and $bb(8)$? Remark: $bb(6)$ as a trivial lower bound does not count as a suitable ...
-2
votes
1answer
46 views

Probability over decidable languages

Let $\mathcal S$ be the set of all languages over some finite alphabet $\Sigma$. Prove that the probability of a randomly chosen (arbitrary distribution) language has a decider is zero.
1
vote
1answer
101 views

Proof of undecidability of $FINITE_{\text{TM}}$ and $USELESS_{\text{TM}}$

I came across these 2 problems about proving of undecidability of languages: $1$. $FINITE_{\text{TM}} = \{\langle M \rangle | M \text{ is a Turing machine and } L(M) \text{ is a finite language} \}$. ...
1
vote
1answer
126 views

Will this Turing machine ever halt?

Consider the following Turing Machine, $T_k(n)$, defined in terms of: $$ T_k(n) = 1 + T_n(n) $$ At a high level, this expression indiviates that we have a Turing machine (with instructions ...
1
vote
2answers
62 views

Trying to describe this Turing Machine

Let's say I have the following turing machine: $F_n$ = {M | M is a TM and |L(M) ≤ n} In english, for some given natural number n, $F_n$ is the language of all turing machines that accept no more ...
2
votes
1answer
110 views

Why do complex grammars require powerful algorithms?

I am reading a fabulous book on Formal Languages and in the book it says: As the rewrite rules of a grammar become more complex, the algorithm for recognizing the associated language becomes ...
2
votes
1answer
70 views

Unknown symbol '#' in set

I am reading a text on Complexity theory. There is a set whose notation I cannot understand: "Let $\sum$ = {0,1,#}" From the context, and given that the book is used computer science courses, it ...
0
votes
1answer
52 views

problem understanding a solution of Talbot's book (complexity and cryptography)

There's a question which is answered at the end of the book, but I have problem understanding the answer, my own understanding is that its lower bound would be $n^2$ as well. A palindrome is a a ...