# Tagged Questions

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

60 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 ...
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 ...
89 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!
81 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 ...
32 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 ...
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 ...
79 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 ...
18 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 ...
54 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 = {...
86 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 ...
28 views

175 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
77 views

### Have anyone ever thought of continuous analog Turing machine?

Have anyone ever thought of continuous analog Turing machine? The machine adopts continuous (from R) the input data from the tape, It moves to a different state depending on the value on the tape. On ...
77 views

### Understanding Turing Machines: Recognizable and Decidable langauges

I've searched tons of resources and while conceptually I understand the turing machine itself and what it does- I'm a bit stuck on Turing Recognizable and Turing Decidable languages and I'm not sure ...
79 views

### There are more languages than programs?

I am reviewing some Turing machine material...and I come across this the set of all programs are countable (convert them into binary string, each of which represent an integer) whereas the set of ...
31 views

### Deciding set of all Turing machine codes of TMs accepting languages of cardinality $\leq 10$.

Problem: I need to show that the following language is decidable and if not, if $S$ or $\overline{S}$ is partialy decidable language. $S=\{w_e\;|\;|L(M_e)|\leq 10\}$ That is set of all Turing ...
42 views

### Unprovable behavior of a turing machine

The wikipedia-article for the P-NP problem [1] says there are three possible answers to the P-NP-problem: $P=NP$ $P\neq NP$ $P=NP$ is independent of ZFC The third possible solution seems to be ...
38 views

### Do there exist infinite sets of non-halting programs such that every program in the set computes every other program in the set?

Do there exist infinite sets of non-halting programs such that every program in the set computes every other program in the set, and only programs in that set? I know there exist programs which ...
69 views

### How to prove whether a language is decidable and/or semi-decidable (or neither) using reduction?

I think I understand the basics of reduction, however I'm far from confident with using the techniques. I have a couple of examples that I'm struggling with: L1 = {< M > | M accepts an infinite ...
119 views

### Must an algorithm terminate?

I am confused. Sometimes i read about terminating and not terminating algorithms. I almost always read these things in the context of turing machines. This means to me: There are algorithms which ...
40 views

### How could I design a turing machine that prints all natural numbers on its tape in order?

How one could implement a turing machine that prints all natural numbers of its tape in order. Two consecutive numbers are separated on the tape with the symbol #. The tape should look like this: #0#...
39 views

### How could I modify a Turing machine that attempts to move the head past the leftmost square(crash) on some inputs so that it doesn't crash at all?

Suppose that M is a TM that crashes on some inputs. How would I modify M so that the new machine accepts the same language but does not crash on any input ?
62 views

### Show that every finite subset of $\{0,1\}^*$ is recursive [closed]

How can I show that every finite subset of $\{0,1\}^*$ is recursive ?
129 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 ...
30 views

### Does 3-SAT reduce to 3-CNF-SAT?

I know that SAT goes to 3-SAT and SAT is reducible to CNF-SAT and CNF-SAT is reducible to 3-CNF-SAT but is 3-SAT reducible to 3-CNF-SAT? They are not the same thing though right because CNF makes it ...
68 views

### Design a Turing Machine to compute the function

I'm tasked with designing a Turing Machine able to run in this Turing machine simulator With the function: f(x) = { x : x < 3 x + 3 : x ≥ 3 Where input: ...
66 views

### Is a Turing machine on an arbitrary (finite) alphabet equivalent to one on {0, 1}?

Brief context: I'm trying to understand why a Universal Turing Machine exists, on a tape with alphabet $\{0, 1\}$. I think I can see that a $3$-tape Turing machine can represent a Universal Turing ...
24 views

### State Change in a Turing Machine(Computer of Integer Function)

Im trying to learn how TM can be used as a computer of integer functions. I have this problem The text books gives the construction as follows I understand that intially the R/W head will be ...
9 views

### Moves in a Turing Machine

In a Turing Machine i understand that δ(q,x) is a transition function that results in a Change in ID. What does δ(q, Xj) =(P, y, L) mean.I understand that L stands for move left.Is P the new state ...
17 views

### Intersection of Turing Machines Languages

Given a Turing Machine A and a Turing Machine B, how can I know if the intersection of the Languages of both Turing Machines is non empty? L(A) $\cap$ L(B) $\neq$ 0
116 views