# Tagged Questions

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

768 views

### How can Busy beaver($10 \uparrow \uparrow 10$) have no provable upper bound?

This wikipedia article claims that the number of steps for a $10 \uparrow \uparrow 10$ state (halting) Turing Machine to halt has no provable upper bound: "... in the context of ordinary ...
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 ...
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 ...
974 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 ...
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 ...
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?
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 ...
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 ...
12 views

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 ...
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 ...
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 ...
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}$. ...
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 ...
55 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 ...
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, ...
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 ...
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 ...
37 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 ...
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 ...
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 ...
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 ...
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 ...
33 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 ...
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 ...
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 ...
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?
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 ...
31 views