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

I understand Turing Machine things about languages but I don't understand same things about problems and their inputs

I am reading and trying to understand https://jeremykun.com/2012/02/23/p-vs-np-a-primer-and-a-proof-written-in-racket/ and https://jeremykun.com/2011/07/04/turing-machines-a-primer/, and the author ...
0
votes
0answers
15 views

Is there a language not in NP but for which exists a Non-deterministic TM which accepts/rejects strings based on belonging to the language?

Is there a language $L$ such that $L \notin NP$, and $\exists$ Non-deterministic Turing Machine $M$: $\forall l \in L$ : $M$ accepts $l$, $\forall l \notin L$ : $M$ rejects $L$? A side-question. Are ...
1
vote
1answer
31 views

By what measure does the busy beaver function grow faster than any computable function?

It has been proven that the busy beaver function grows faster than any computable function. But I wouldn't think that speed of growth is well-defined. What is the definition? Is there some index?
-1
votes
0answers
24 views

The relativised Church–Turing thesis

Barry Cooper states in his computability theory "The relativised Church–Turing thesis" on page 142 as follows: All formalisations of "$B$ computable from $A$" which are sufficiently reasonable ...
0
votes
1answer
13 views

Is $\{\langle M \rangle \mid \exists P \;\text{(p is polynom)}\; \forall w\; \text{M(w) halt with less than p(|w|) steps}\} \in RE$?

Is $L=\{\langle M \rangle \mid \exists P \;\text{(p is polynom)}\; \forall w\; \text{M(w) halt with less than p(|w|) steps}\} \in RE$? I can prove that $L \notin coRE$, but I don't know what to do ...
0
votes
1answer
12 views

Is $\{\langle M \rangle \mid \exists K \forall w\; \text{M(w) halt with less than K steps}\} \in RE$?

Is $L=\{\langle M \rangle \mid \exists K \forall w\; \text{M(w) halt with less than K steps}\} \in RE$ ? I can prove that $L \notin coRE$, but I don't know what to do about $RE$... ($L \in coRE \...
0
votes
0answers
12 views

Change In Time from Bidirectional Turing Machine to Standard Turing Machine

I'm reading this book on Computational Complexity and on page 37, it has a proof that a bidirectional TM $M$ running in $T(n)$ time can be converted to a unidirectional TM $\widetilde M$ running $4T(n)...
1
vote
0answers
3 views

Turing machine with k-dimensional tape or k-regular tree

The statement I read is " In a k-dimensional tape, cells corresponds to elements of free commutative group of k generators. s. There are 2k shifts, which correspond to addition of a generator ...
0
votes
1answer
35 views

comparing two strings with Turing Machine

Reading about Multitape Turing Machines and coming across this exercise: Construct a Turing Machine, that can "tell" if a word w1 on strip 1 matches w2 on strip 2. Given approach : Compare the states ...
0
votes
1answer
41 views

Not sure about Turing machine

Not quite sure, if I understand Turing machine correctly. So I tried building one, which should give back the predecessor of a number in binary code. e.g. 111 -Turing-> 110 picture of turing m. If ...
0
votes
0answers
32 views

Modified version of SubsetSum

Let $L=\{(y_1,...,y_n,S,p)\ |\ \exists I\subset[n]\ s.t. \ |I|=p.\ \sum_{i\in I}y_i=S\}$. and $\forall\ 1\leq i\leq n\ :y_i \text{ is a positive integer}$, Assuming $\mathcal{P}\neq\mathcal{NP}$. ...
0
votes
1answer
20 views

Difference between Turing unrecognizable and Turing undecidable language

I get the fact that due to diagonalization argument number of language is uncountable and since TM are countable, hence there are some language which is not recognized by the Turing machine. I also ...
-1
votes
1answer
54 views

$L\in P$ prove that $L^*\in P$

I have that question that looks kinda easy at first but it is quit hard. Let $L\in P$ prove that $L^*\in P$ (L is a language and P is the class of all problems which can be decided by a ...
0
votes
0answers
20 views

Find the classes of $L_1=\{w|n_a(w)|n_b(w)=n_c(w)\}$ and $L_2=\{wxw^R|w,x\in(0,1)\}$

$L_1=\{w|n_a(w)|n_b(w)=n_c(w)\}$ $L_2=\{wxw^R|w,x\in(0,1)\}$ My attempt: $L_2$ seems regular since it's finite. $L_1$ is DCFL since we can identify strings of $L_1$ using single stack, first we ...
0
votes
1answer
27 views

Subset of regular language $a^*$

Given $L\subseteq a^*$, then $L$ is definitely decidable $L$ is definitely Turing – recognizable $L$ may not be Turing – recognizable. $L$ is regular My attempt: $L$ may not be regular, ...
0
votes
1answer
34 views

Design a Turing Machine which finds center of a given string with even length

A Turing machine is an abstract machine that manipulates symbols on a strip of tape according to a table of rules; to be more exact, it is a mathematical model of computation that defines such a ...
1
vote
0answers
36 views

Turing Machine make use of another Turing Machine

I am expected to formally construct a deterministic TM to compute a function. I already have a TM for $f(x)$. How can I make use it formally while constructing $g(x)$? $g(x)$ is like in the followig ...
2
votes
1answer
34 views

Countable State Automata

Consider an automaton with a countably infinite number of states. This machine could, given it's current state and a symbol from the input alphabet, move to another arbitrary state in a finite amount ...
1
vote
2answers
92 views

How large must $S(5)$ be at least , if it is not $47,176,870\ $?

See here : https://en.wikipedia.org/wiki/Busy_beaver for more details about the maximum-shifts-function It is said that about $40$ machines with $5$ states have unknown status (it is not known ...
0
votes
0answers
21 views

How to find Turing Machine for given arbitrary output

Are there general methods / algorithms for finding a Turing Machine that will output a given binary number? For example, I want the machine to write ...
1
vote
1answer
35 views

A Question about Computable Functions

Barry Copper states following in his Computability theory book which I have a question about them. Exe.4.5.1: Show that if $\varphi_e(x) \downarrow $ is a computable relation, then so is ...
0
votes
0answers
17 views

Determine to which class $\left\{\langle M\rangle\Big\vert L(M)\in RE\setminus R \right\}$ belongs

As stated in title I want to determine to which class $$S=\left\{\langle M\rangle\Big\vert L(M)\in RE\setminus R\right\}$$ belongs. I believe that $S\notin RE\cup\text{co}RE$. In order to ...
0
votes
1answer
31 views

Determine whether a language belong to R,RE\R,coRE\R or other

For the following language, determine to which class it belongs $$L_3=\left\{\langle M\rangle\Big\vert|\langle M\rangle|\le 2016\text{ and M is a TM that accepts }\varepsilon \right\}$$ I've ...
0
votes
0answers
17 views

Tag systems to cyclic tag systems and turing completeness

Consider the 2-tag system Alphabet: {a,b,c} Production rules: a --> bc b --> a c --> aaa and stating words aaa...a halts. on ...
0
votes
0answers
28 views

Are these functions computable - Understanding computable functions

There is a theorem in computability theory which states: B.Cooper: If $A\subseteq N$ is computable, then $A$ is also computably enumerable. In the proof of this theorem -which is an ...
-3
votes
1answer
26 views

Deterministic Turing Machines

Let's say that M is a deterministic Turing Machine, can I say that for a certain input I will have the same output? How can I demonstarte this?
0
votes
1answer
25 views

A Question About Recursive Functions

We want to find a recursive function $f(x,y)$ in order to have this equality: $$ \mathbf \varphi_{f(x,y)} = \varphi_x + \varphi_y$$ I know we should use "s-m-n" theorem, but I can't find the ...
0
votes
0answers
31 views

How to derive Turing Machine language?

Say you're given a TM (Turing Machine) $M = (Q, \Sigma, \Gamma, \vdash, \sqcup, \Diamond)$ and given the partial $\delta$: $$\begin{array}{c|cc} \delta&\vdash&a&b&c&\sqcup&\...
2
votes
0answers
37 views

Are the derivatives of the Busy Beaver function positive?

Let $BB:\mathbb Z_{\ge1}\to\mathbb Z$ be the Busy Beaver sequence, usually called the Busy Beaver function, as defined in terms of Turing machines in Section 1.3 of this text of Aaronson and Yedidia. ...
1
vote
0answers
24 views

Equivalence of Turing Machines and Lambda Calculus

Based on the Church Turing Thesis, we conjecture that Turing Machines are the "correct," model of computation. It is well known that they are equivalent to the Lambda Calculus, another model of ...
0
votes
1answer
44 views

Induction with Turing machines.

how would I go about proving by induction that the Turing Machine pictured below, that if it is started with a blank tape, after 10n+6 steps the machine will be in state [3] with the tape reading . . ...
2
votes
1answer
35 views

Turing Machine Diagram, one Solved Problem ?!

The following Diagram Gets binary number $x$ and produce $x+1$. complete it: the book solution is says first line is the answer. any hint or idea for completing this TM?
2
votes
1answer
56 views

What is the smallest number $n$ for which $bb(n)>f_{\epsilon_0}(5)$ is known?

It is known that $bb(23)$>Graham's number (I do not remember exactly, but $bb(21)$ could already be larger). But what is the smallest number $n$, such that $bb(n)>f_{\epsilon_0}(5)$ is known ? ...
0
votes
1answer
22 views

Demonstrate that a language is semi-decidable

I need some help to demonstrate that this set below is decidable, semi-decidable, or undecidable. Here's the set: H = {p| |Images(fp)| >= 10} explanation: an ...
0
votes
1answer
25 views

Algorithm with undecidable input set?

I am interested in "Relative Decision Problems" in the following sense: Let $\mathbb{N} \supseteq U \supseteq S$. Is there an algorithm such that on a given input $u \in U$ decides whether $u \in S$? ...
1
vote
0answers
22 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
37 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
40 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
30 views

Construct a turing machine that accepts L = {ww : w belongs to {a,b}*} [closed]

Construct a Turing machine that accepts $L = \{ww : w \in \{a,b\}^*\}$?
0
votes
0answers
20 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 bigger ...
0
votes
0answers
41 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
42 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
40 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
0answers
22 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 ...
0
votes
1answer
36 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 ...
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
22 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
38 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
2answers
39 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