The Stack Overflow podcast is back! Listen to an interview with our new CEO.
21

I'm a bit confused by your question: you're asking if the Turing machine is recognizable, but I think you mean to ask if the language $\{1^x \mid x \in \mathbb{N}\}$ is recognizable. A language is recognizable if and only if we can build a Turing machine that accepts every string in the language, and does not accept any string not in the language. And we ...


8

I believe that this answer by Yuval Filmus all the questions you have asked. If P=NP then any non-trivial set is NP-hard (other than the empty set and the complete set), so assume P$\neq$NP. If $A$ is a set and $f_i$ reduces SAT to $A$ in polytime, then $f_i$ must have infinite range. Otherwise, we can hardcode the relevant values of $f_i$ to get a ...


8

A popular reference is the article Undecidable Problems for Context-free Grammars by Hendrik Jan Hoogeboom. The following is a proof taken from this note by Rob van Glabbeek. Theorem: It is undecidable whether or not the languages generated by two given context-free grammars have an empty intersection. Proof: By a reduction of post correspondence problem (...


6

You do not yet understand what Turing completeness means. Turing completeness is the ability to perform arbitrary finite computations. To simplify matters, we say an arbitrary finite computation is an effective procedure that, given some (finite) input, produces some (finite) output, after some (finite number of) steps. To simplify matters further, we ...


6

Languages are sets of finite strings. Every input to a Turing machine is a finite string. $1^\infty$ is a thing, but not in this model of computation (and usually we're more specific about what infinity we're talking about).


5

Post correspondence problem can be solved using a brute force approach. No. Brute force can be applied only if the number of dominoes we are going to use, is finite. For example, if we restrict each domino to be used at most once, then the number of possibilities will be finite and we can use a brute force algorithm. But the PCP allows us to use each ...


5

Your exam question makes very little sense. The obvious reading would be this: Let $M$ and $N$ be two Turing machines. Why is it not possible to prove that $M$ and $N$ compute the same function? More precisely: It is not the case that for all Turing machines $M$ and $N$ it is provable that $M$ and $N$ compute the same function. Well, this is quite ...


4

No, if $L_1\cup L_2$ is decidable $L_1$ and $L_2$ are not necessarily decidable. Here's an example. $$\begin{align} L_1 &= \text{any language that is not decidable.}\\ L_2 &= \Sigma^*\setminus L_1. \end{align}$$ $L_1\cup L_2$ is $\Sigma^*$, which is decidable. However, $L_1$ is not decidable. In fact, $L_2$ is not decidable, either. The proof ...


4

You haven't defined HALT, so let me assume that it consists of all Turing machines that halt on the empty input. If $M$ halts in time $f(n)$, then in particular it halts on the empty input, and so if $M$ belongs to your language then it also belongs to halt. But the converse doesn't hold, and $L \subseteq HALT$ doesn't imply anything about $L$ (for example, $...


4

The inference "the universe would be completely computable, so no undecidable/uncomputable things could exist" is invalid. In the effective topos, where everything is computable, there are many undecidable phenomena. For example, all real numbers are computable, but equality of real numbers is undecidable (and computable). To give you an idea how this ...


4

If $A=\{0,1\}^*$ then $A\cup B=\{0,1\}^*$, regardless of what $B$ is. $\{0,1\}^*$ is decidable, and choosing to express it as something involving undecidable things doesn't change that fact. The question "Is $w$ in $A\cup B$?" is equivalent to "Is at least one of the following statements true? $w$ is in $A$; $w$ is in $B$; $w$ is in both $A$ and&...


3

You are correct. The problem of deciding "$L$ is a recursively enumerable language" is undecidable. However, that does not make $L$ itself undecidable. Do not mistake a language for its class! Telling whether $L$ is in a class is definitely not the same as deciding membership in $L$.


3

Let $\gamma_{ij},\delta_{ij}$ be the number of characters $\sigma_j$ in $\gamma_i,\delta_i$ (respectively). Then the PCP instance has a solution if there exist non-negative integers $a_1,\ldots,a_N,b_1,\ldots,b_N$ such that for all $j \in \{1,\ldots,K\}$, $$ \sum_{i=1}^N a_i \gamma_{ij} = \sum_{i=1}^N b_i \delta_{ij}. $$ While integer programming is hard ...


3

Let $K$ be some undecidable problem, and define $$ L = \{0x : x \in K \} \cup \{1y : y \notin K \}. $$ (I'm assuming the alphabet is $\{0,1\}$.) Then $$ \overline{L} = \{\epsilon\} \cup \{0x : x \notin K \} \cup \{1y : y \in K \}. $$ I'll let you take it from here.


3

Interesting question. Factorization of functions, including factorization of polynomials is in fact a classical problem throughout history of mathematics. For the sake of contradiction, assume that $$x^2 + y^3 - e^{z} = f(x)*g(y)*h(y,z)$$ For the sake of simplicity, assume that $f, g, h$ are continuously differentiable inside $D$, the place where we are ...


3

Any program and input pair can be converted to a program without input by just including the input in the program, so if the halting problem is decidable for programs without input, then it is decidable for all program and input pairs.


3

If you are interested in the effect of being able to compute with continuous real numbers, you might enjoy learning about the Blum-Shub-Smale theory of computation with the reals. A good survey is Computing over the Reals: Where Turing Meets Newton by Lenore Blum. Wikipedia states that the set of functions that are computable in this model are incomparable ...


3

This is a situation where coding is non-trivial. $\mathcal{C}_T$ is a class of decidable languages. To make sense of $\mathcal{C}_T$ having any effective properties, we need to choose a coding. Naturally, we would code some decidable language $L$ by the index of some TM that decides it. So what does it mean for $\mathcal{C}_T$ to be recursively enumerable? ...


3

Do we ever take into consideration a word with infinite length during such analysis? Never say never. However, it is a safe bet that in the course of your undergraduate or even graduate study you can assume that all inputs to Turing machines are finite. Here is a more formal restatement/understanding of the problem in the question. $$\begin{align}\text{...


3

Yes, your thought is correct. The only missing part, as you pointed out, is whether or how we can create a CFL algorithmically for the intersection of a CFL with a RL. If you take a close look at any proof for the fact that the intersection of a CFL with a RL is a CFL, you will find that the proof is constructive or can be made to be constructive easily, ...


3

There are two important misunderstandings in your question. You talk about "the Turing machine" for a language but there isn't just one: in fact, if a language is recursive (or RE) then there are infinitely many Turing machines that decide (or accept) it. If a Turing machine decides a language $L$ then, by definition, it accepts every input in $L$ ...


2

In short, A LBA has finite number of configurations, say D. Hence, we can run for D steps and conclude the result. If it runs for more that D steps, by pigeonhole principle, we can say that, it is stuck in an infinite loop.


2

Well, I would like to ask the same kind of question to you. Why did Sebastian Oberhoff have to define a computational model before demonstrating undecidability? I will answer the above question on behalf of you below, assuming an imaginary line of case development. Of course, you might answer better than me. Of course, to prove some kind of undecidability,...


2

Without fixing a concrete model of computation, you can't show that you can actually do the "then construct" part of your argument, so it's not a proof.


2

Your language is indeed co-c.e.; the mistake is in the argument claiming recognizability of $L$. You have the existential and universal quantifier mixed up.


2

Recall that $A \leq_m B$ iff $\bar A \leq_m \bar B$. Indeed, the same reduction function works for both cases. So, let $H$ be the halting problem. Both $H,\bar H$ are undecidable. We prove $H \not\leq_m \bar H$. By contradiction, assume $H \leq_m \bar H$. Hence, by the property above, $\bar H \leq_m H$. Hence $\bar H$ reduces to some RE problem, making $\...


2

Let us express $L$ slightly more precisely. $$ L=\{<TM>\; \mid \text{The language accepted by } TM \\ \text{ is a recursively enumerable language}\}$$ Since for any Turing machine $TM$, the language accepted by it is a recursively enumerable language by definition, that restriction clause for $TM$ does not have any effect at all. We have, as indicated ...


2

"Turing complete" is defined as "able to do everything a Turing machine can do, if you give it enough resources". All modern programming languages are either Turing complete or "effectively" (*) Turing complete, simply because it's hard to be a useful programming language without that. In particular, if you have… Some basic means of doing arithmetic, like ...


2

It is possible for $A$ & $B$ to be mutually exclusive and yet be exhaustive. Now this can happen even when one of them is not decidable. So option A. The analysis above is correct except the last conclusion "So option A". We cannot exclude the possibility that $A$ and $B$ are both decidable. In fact, it happens in the current situation because of the ...


2

By definition, $\bar A = \{w \ |\ M \mbox{ halts on } w \}$, which is recognizable: we run $M$ on $w$, accepting if it ever halts (and diverging otherwise). So, the complement of $A$ must be recognizable. We now need to understand what class $A$ might belong to. Take the trivial case where $B=\emptyset$ (which is decidable). This can be recognized by a TM $...


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