Episode #125 of the Stack Overflow podcast is here. We talk Tilde Club and mechanical keyboards. Listen now

# Tag Info

3

If you give a word $w$ not in the language, then the TM is not guaranteed to halt as an NPDA isn't always guaranteed to terminate in finite steps for a finite word. So, you can produce a counter example in which your construction doesn't work. Take an NPDA which doesn't terminate for a given word (exists, of course) and run your algorithm on that word. ...

2

Sipser's book handles this case: If at any point $S$ moves one of the virtual heads to the right onto a $\#$, this action signifies that $M$ has moved the corresponding head onto the previously unread blank portion of that tape. So $S$ writes a blank symbol on this tape cell and shifts the tape contents, from this cell until the rightmost $\#$, one unit ...

2

Enumerate all turning machines $M_1, M_2, \dots,$ and simulate them in a dovetail fashion, i.e., proceed in rounds: In the first round simulate $M_1$ for $1$ step; In the second round simulate $M_1$ and $M_2$ for one (more) step each; In the third round simulate $M_1$, $M_2$ and $M_3$ for one (more) step each; ... In general, at the $i$-th round you ...

2

As an example where unbounded loops are needed: I can write an emulator for any machine, running in a loop. With unbounded loops, that emulator can run forever. With bounded loops, I must calculate beforehand how long that emulator runs. That calculation might return "the simulator will run for one trillion trillion trillion years", which in theory makes a ...

2

Real world computers are not Turing complete (they have a finite amount of memory) and are equiparable to Linear Bounded Automata. So the easiest way to design a non-Turing-complete language is to design a language that has only a limited amount of memory (the memory can also be a function of the input length) and don't worry about other restrictions. But ...

2

You're almost there. Yes, the intersection of two context-free languages is in general not context-free, but you have more structure here: one of your languages is regular! The intersection of a regular language and a context-free language is context-free, which gives us something to work with. So. We have some DFA $M$, and we can build a PDA $N$ which ...

2

Nothing special happens if the Turing machine doesn't read the entire input. For example, the machine can halt immediately, without looking at the input at all. If the Turing machine halts at an accepting state, then the input is accepted. If it halts at a rejecting state, then the input is rejected. In this way you can construct a Turing machine that ...

2

Original Question: $L_1 = \{w \in \{0|1\}^* | \text{ w is a sequence of one or more 1's } \}$ $L_2 = \{\langle M \rangle | \text{ Turing machine } M \text{ decides } L \}$ prove that $L_2$ is undecidable. Answer: For first part you are correct. First language $L_1$ is indeed decidable. Actually it is regular as represented by regular expression $1^+$. ...

2

Perhaps the simplest way is to implement the following algorithm: Initialize $y$ to 0 Initialize $n$ to 0 Compare $y$ to $x$; if $y = x$, accept; if $y > x$, reject; otherwise, continue Add $2n+1$ to $y$ Increment $n$ by 1 Jump to 3 The idea is that $y = n^2$ always. This is ensured using the formula $(n+1)^2 = n^2 + (2n+1)$.

1

There is an important gap between human reasoning ("high level") and the formal definition of a Turing Machine ("low level"). If you are approaching these exercises for the first time and you are not yet familiar with TMs, what I recommend is to write down a pseudocode description of the algorithm which is nothing more than a high level description of the ...

1

Designing a Turing machine is very laborious, even for simple tasks. So I suggest you keep the algorithm as simple as possible, even if it is very inefficient. The very simplest prime generating algorithm (even simpler than the sieve of Eratosthenes) is as follow: Start with $n=2$ - this is prime. Set $j$ equal to $n$. Add $1$ to $n$ Set $k$ equal to $n$. ...

1

I will assume that your tape alphabet is $\Sigma = \{0, 1, "\,"\}$, where the last character is a space. Also, it is not clear if a word in the language must start with a $0$ and end with a $1$. In the following I will assume so (it should be easy to modify the machine to remove one or both of these constraints). The Turning Machine is $\langle \{y,n,q_0,... 1 Here is a reduction from coHALT (given a Turing machine, determine whether it doesn't halt on the empty input) to$L$. Given a Turing machine$M$, construct a new Turing machine$M'$which acts as follows: Run$M$on the empty input. If$M$halts, interpret the input as a Turing machine and run in on the empty input. If$M$doesn't halt on the empty input, ... 1 You cant find the complement of a$TM$for undecidable languages. A decidable language is such that a$TM\$ which recognizes language membership, always halts with a yes. In this case finding the complement of the machine is simple, just reverse the yes with the no, obtaining the complement of the original decision problem. I leave to you the task of ...

Only top voted, non community-wiki answers of a minimum length are eligible