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
14 views

$K(xy)\leq K(x)+K(y) +c$?

Could anyone show that for any $c$, some strings $x$ and $y$ exist, where $K(xy)>K(x)+K(y)+c$? Here $K(x)$ is the Kolmogorov complexity. I already know that $K(xy) \leq 2K(x) + K(y) +c$ and $K(xy) ...
0
votes
1answer
25 views

Is the problem decidable with Turing machine M that inputs x,y,z does M halts on these 3 instances

Is the following problem is decidable? Given a Turing machine M inputs x,y,z does M halts on these 3 instances? Hint: make y and z any two artificial inputs that the program stops with these inputs. ...
0
votes
1answer
25 views

Using reductions of turing machines properly

I recently learned about reductions of Turing machines (here after TM), and here is a solution to a problem using reduction (showing L is undecidable, as defined bellow). I have given the reduction, ...
-2
votes
2answers
18 views
0
votes
0answers
11 views

Is the Antikythera Mechanism Turing-Complete?

Is the following Turing-complete? https://en.wikipedia.org/wiki/Antikythera_mechanism As in, it possible to perform all of the operations of a Turing-machine, albeit with finite memory, with this ...
0
votes
0answers
21 views

simple questions on $TM$s runs lengths

Is it possible that the number of running steps in $TM$ that runs on word $w$ will be $0$? Is it possible that the number of running steps in $TM$ that runs on the empty word $\epsilon$ will be ...
0
votes
0answers
35 views

Prove that a certain intrinsic property of Turing machines is not decidable

Can anyone help me to prove that the following language is nod decidable? $$ A=\{\langle\,M,w,q\,\rangle\mid M \text{ is a $TM$ , $w$ is a word, $q$ is a state in $M$ and while $M$ runs on $w$ it ...
0
votes
0answers
40 views

Classifying languages

I'm working on understanding what kind of languages are decidable, recognizable, and co-recognizable. I came across this problem that I think will really help me but I'm still quite unsure of how to ...
1
vote
1answer
36 views

Is the union of undecidable languages not Turing-recognizable?

The question is as follows: Let us define $$L := \{w \mbox{ | either }w = 1x \mbox{ for some } x \mbox{ ∈ $A_{TM}$ or } \mbox{$w$ = 0$y$ for some $y$ ∈ $\overline {A_{TM}}$}\}.$$Prove that neither ...
0
votes
1answer
45 views

Design Turing Machine

Design a single-tape Turing machine with input alphabet {0, 1} to decide the language $$\{ x\in\{0,1\}^* \mid \#(0,x)=2\cdot\#(1,x)\}.$$ Could someone give me clarification on how to approach and ...
0
votes
1answer
32 views

proof that languages are/are not in RE (probably with mapping reduce)

Given $2$ languages: Let $u \in \Sigma^*$ (constant word). $A_u=\{<M> \big{|}\,\, u\in L(M) \text{ and M is TM }\}$ $B_u=\{<M> \big{|}\,\, L(M)=\{u\} \text{ and M is TM }\}$ I ...
0
votes
0answers
20 views

Prove uncountability of set L that L and L' neither of which is recursively enumerable.

How do I prove that the set of all languages L on alphabet {0,1} that neither L or L' are recursively enumerable, is uncountable? Proving uncountability can be done through diagonalization like the ...
1
vote
1answer
14 views

Is each string decideble?

Is it possible to prove that there exist for every string a Turing Machine that decides that string? I think it is provable that for every string you can build a TM that recognises that string, but I ...
1
vote
0answers
20 views

turing machine decidable description for the language

L = { | R is a regular expression that produces at least one word in {a, b} * which contains a symbol exactly 3 times} ...
0
votes
1answer
31 views

turing machine decidability language

I must show that this language is decidable but I think it's not {D, Ρ} | D is a DFA and P is a ΡDA which L(D) ∩ L(Ρ) = ∅ } Here what I think I give a reduction from E(TM). I suppose that this ...
1
vote
1answer
104 views

Turing Machine That Accepts Machines With Undecidable Languages

So I'm reviewing my Computability notes for my final, and I understand how reduction arguments work, but I'm having trouble framing one for the following Turing machine: Undecidable TM = { ⟨M⟩ | L(M) ...
0
votes
1answer
787 views

Showing that Turing-recognizable languages are closed under union

I'm reading "Theory of Computation" by Michael Sipser and I've encountered a solution (provided by the book) that I don't understand. The question: Show that the collection of Turing-recognizable ...
1
vote
2answers
34 views

Automatic proof verification by a Turing machine

Is it possible to automatically verify a mathematical proof? Or is it proven that this cannot be done by a Turing machine? Thank you very much Kevin
0
votes
0answers
34 views

Turing machine macro notation

This is an example from the book Automata, Computability and Complexity by Elaine Rich. Macro language is defined as follows: (screenshot from the book) And these are the steps mentioned : Scan ...
0
votes
1answer
86 views

Prove claims about disjoint union and decidable/undecidable languages

Let $L\subseteq\Sigma^*$ decidable language and $A\subseteq\Sigma^*$. Let $B=A\sqcup L$ (a disjoint union). Prove: $1$. $B\in RE \Rightarrow A\in RE$ $2$. $B\in R \Rightarrow A\in R$ Thanks!
0
votes
0answers
16 views

Prove by printing turing machine that RE closed under iteration

I do not know what is the formal name of printing turing machine in english, maybe "counter machine". This machine prints a whole language without any input. for example: counter machine that counts ...
0
votes
1answer
62 views

non deterministic turing machine for concatenation

Let $L_1, L_2$ decidable languages on deterministic single-tape TM $M_1$ and $M_2$. How can I build non-deterministic TM that decides $L_1L_2$? What should be the formal definition of $\delta$ (the ...
0
votes
1answer
22 views

Drawing a state diagram for a Turing Machine

I'm a bit rusty since it's been a couple weeks since I've last done this, but I could really use some help with starting out the Turing Machine for {a^i b^j c^k | i = j + k} I'm confused on how I can ...
4
votes
2answers
78 views

Why is it so hard to translate some proves into machine-readable form?

I have just read a topic on mathoverflow about man vs. machine in mathematics. The topic was inspired by the recent victory of Alpha Go over the World Go Champion, Lee Sedol. It reminded me of an ...
0
votes
0answers
20 views

Is there a universal Turing machine on arbitrary number of input variables?

I know that for every $n \geq 1$ there is a partial recursive (p.r.) function $\phi^{(n+1)}_{z_n}(e,x_1,...,x_n)$ such that $\phi_{z_n}^{(n+1)}=\phi_e^{(n)}(x_1,...,x_n)$, where $\phi_e^{(n)}$ is the ...
1
vote
1answer
16 views

Cannot create algorithm for decidable language

L2 = {<M> : M is a TM and there exists an input string w such that M halts within 10 steps on input w} Hi. I am creating an algorithm to show above L2 is ...
0
votes
1answer
34 views

Cannot understand solution (Turing Machine & Reduction)

Photo of my problem that I don't understand About question above in photo, I just can't understand its solution provided. We know the complement of Atm = {...
2
votes
1answer
61 views

Problems understanding proof of s-m-n Theorem using Church-Turing thesis

I am reading Barry Cooper's Computability Theory and he states the following as the s-m-n theorem: Let $f:\mathbb{N}^2\mapsto\mathbb{N}$ be a (partial) recursive function. Then there exists a ...
0
votes
1answer
40 views

Reduction to/from REC and RE language?

Let $X$ be a recursive language and $Y$ be a recursively enumerable but not recursive language. Let $W$ and $Z$ be two languages such that $\overline{Y}$ reduces to $W$, and $Z$ reduces to ...
2
votes
1answer
22 views

Space-Hierarchy Theorem in Theoretical CS

Sipser has a proof this theorem that goes like this: $$D = \text{"On input } w$$ $$1. \text{Let } n \text{ be the length of } w$$ $$2. \text{Compute } f(n) \\ \text{using space constructibility and ...
1
vote
1answer
32 views

Which language is decidable

Just been at the Math-exam. One question I was really unsure about, was this question - so I didn't answer it, as you get minus point if the answer is wrong. Does somebody know, what the right answer ...
1
vote
1answer
52 views

How is the non-existence of a solution proven?

I've been wondering how an argument that a solution to a particular problem doesn't exist is put together. For instance "Pour-El and Richards found an ordinary differential equation ...
0
votes
1answer
102 views

Read-only Turing machine recognizes only regular languages?

Show that the Turing machines, which have a read only input tape and constant size work tape, recognize precisely the class of regular languages. According to wiki : A read-only Turing machine or ...
0
votes
1answer
56 views

Showing set is undecidable with Turing Machines

I'm given the set $T = \{\langle M, w\rangle : M $ is a Turing Machine that accepts $w$ reversed whenever it accepts $w \}$ and I want to show it's undecidable but recognizable. (I'm using the bracket ...
1
vote
2answers
55 views

Is there a way to prove that a Turing machine computes the function we designed it to?

Say we design a simple Turing machine that adds two numbers together. Is there any way to formally prove that the machine actually computes the function we 'know' it does? Is there a general method ...
2
votes
1answer
13 views

Savitch theorem and its assumption

famous Savitch theorem states: For any function $f\in\Omega(\log(n)), \text{NSPACE}(f(n)) \subseteq > \text{DSPACE}((f(n))^2).$ Why we need an assumption that $f\in\Omega(\log(n))$? Thank ...
3
votes
1answer
44 views

Abstract machines that compute primitive recursive functions

What it the simplest (least powerful) abstract machine that can compute primitive recursive sets, i.e. sets whose characteristic or indicator function is primitive recursive? ...
1
vote
1answer
24 views

Turing recognizable - $B = \{a^n b^n c^n \}$

Question: My answer is no, because it loops forever. But I am a bit unsure if this is the right answer.
2
votes
2answers
297 views

Milton Green's lower bounds of the busy beaver function

Wikipedia states that Milton Green demonstrated in 1964, that the busy beaver function $\Sigma(n)$ has the lower bound $$\Sigma(2k)>3\uparrow^{k-2}3$$ I read the talk about the busy beaver ...
0
votes
0answers
37 views

all recursive functions are turing computable

I'm studying with the book computability and logic(boolos). In chapter 5, the theorem is proved, indirectly, by showing that (recursive => abacus) & (abacus=> turing). But I want to prove ...
1
vote
1answer
37 views

How is $ BPP = BPP_{1/2+n^{-c}}= BPP_{1-2^{n^{-d}}} $

I'm not able to understand how $BPP = BPP_{1/2+n^{-c}}= BPP_{1-2^{n^{-d}}} $ Can any body explain this to me in simple terms. Any help on this is highly appreciated.
2
votes
0answers
45 views

How are weakly universal Turing machines actually defined?

For what I know, the definition of a universal Turing machine is something along the lines of the following (of course, details might vary from source to source): A Turing machine $M$ is called ...
1
vote
1answer
95 views

A function given a string ( a program) accepts it if the next program which halts does so in an odd number of steps… is it turing computable

A function which given a string returns 1 if the next program halts with an odd number of steps and 0 otherwise. Is this function computable f(s)=1 if w halts in odd number of steps where w>s and ...
0
votes
0answers
79 views

Designing a Turing machine for Binary Division

I'm trying to design a TM to binary divide 2 numbers. The best approach I've found is the method: division as repeated subtraction, but I don't know if there's a fastest way or an easier way. ...
3
votes
1answer
208 views

Whats the connection between Turing machine and First order logic?

Today in my Computing class i came across the theorem which states that., If language $L$ and $\Sigma^*\setminus L$ are recursively enumerable then L is recursive (total turing machine). Which looks ...
0
votes
2answers
72 views

Is this integral less than infinity?

Assume the following integral: $$ \int\limits_{-\infty}^{\infty}\frac{f\left(x\right)} {BB\left(\lceil abs\left(x\right)\rceil\right)}\mathrm{d}x $$ Where $f\left(x\right)$ is any computable ...
4
votes
1answer
43 views

Doubt about neural networks that allegedly compute beyond the Turing limit

The question is about a new result by Cabessa & Siegelmann. http://binds.cs.umass.edu/papers/2014_cabessa.pdf : "In this context, we show that the so-called plastic recurrent neural networks ...
0
votes
0answers
26 views

How to compute the solution for this linearized diffusion-reaction system (separation of variables)?

Let $\Omega=(0,a), a>0$ and functions $u(x,t), v(x,t)\in\mathbb{R}$. Consider the diffusion-reaction system $$ \partial_tu=\Delta u+\gamma f(u,v)\text{ for }x\in\Omega,t>0\\\partial_t v=d\Delta ...
4
votes
2answers
4k views

Build a deterministic turing machine to decide L = { ww }

As the title says. w is in {a, b}^*.Note that I am not looking for the non-deterministic one. Use a Turing machine of one tape and "pointer". An idea: I thought that I would do something like ...
2
votes
3answers
132 views

Turing Machine divisibility by 6 [closed]

I need to design a TM to check if a binary number can be dividied by 6. I don't know how to design it. Thanks