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

0
votes
0answers
28 views

A turing machine which computes the same language as a “stay put” turing machine

Im not sure I really understand how stay put machines work. I know they are just like turing machines but with states. So they can "stay put". But what confuses me is when you define a FSA for a ...
1
vote
2answers
61 views

Decidability of Recursively Enumerable Languages

I'm having trouble with this problem, I know that every decidable language is recursively enumerable but that not every recursively enumerable language is decidable. What are the steps involved in ...
0
votes
1answer
35 views

Turing Machines and Decidability

I saw this question in a textbook on decidable languages, and I was wondering how you would go about solving this type of question: Assume L1 and L2 are decidable languages. Which of the following ...
1
vote
1answer
57 views

Show that the Turing machine will solve the self-halting problem

Suppose we have Turing machine $M^*$ that: i. halts printing 1 if $M_n$ halts on input 1 ii. halts printing 0 if $M_n$ doesn't halt on input 1 Show that you cannot construct $M^*$. ...
1
vote
1answer
35 views

Proof that such a Turing machine cannot be constructed…

Prove there can be no Turing machine $M^*$ that takes input $n$ and: i. halts printing 1 if $M_n$ halts on input 1 ii. halts printing 0 if $M_n$ doesn't halt on input 1 Intuitively I can see why ...
1
vote
1answer
27 views

What is the Church-Turing thesis?

Every source I look at online says something vague about Church's notion being equivalent to Turing's, but what exactly is the Church-Turing thesis? As I understand, it attempts to precisely define ...
1
vote
1answer
54 views

Prove $L$ = $\{\langle M \rangle$ | $M$ is a TM over $\{0,1\}$ and $\langle M \rangle \langle M \rangle \notin \mathcal{L}(M)\}$ is undecidable.

Was stuck on this for a bit so I need to know if I am on the right track. To show that $L$ is undecidable we will show that $\overline{L}$ is undecidable instead. Suppose $\overline{L}$ is decidable ...
1
vote
3answers
70 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
67 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
69 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
78 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
87 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
24 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
36 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
45 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
75 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
48 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
89 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
50 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
45 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
62 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
94 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
221 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
46 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
39 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
46 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
78 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
50 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
36 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
38 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
71 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
114 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 ...