# Tagged Questions

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

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 ...
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

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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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

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 ...
40 views

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 ...
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} ...