Questions related to computability theory, a.k.a. recursion theory

learn more… | top users | synonyms

0
votes
0answers
9 views

Is there a broader class of total functions than $PR$?

In total functional programming programs are restricted to total computable functions. A well-known class of total functions are the primitive recursive functions ($PR$). However the Ackermann ...
-4
votes
0answers
16 views

Is a union of any TM language and the halting problem language decidable

I need to find if the following language is decidable (in $R$): $L=\{ \langle M \rangle \mid M \text{ is a TM}, L(M)\cup H_{TM}\in RE\}$ Where $H_{TM}$ is of the halting problem. My intuition is ...
0
votes
0answers
28 views

Classify the set of all TMs whose languages reduce to A_TM

Let $$L = \{ \langle M \rangle \mid M \text{ is a Turing machine so } A_{TM} \leq_m L(M) \}$$ The question is whether $L$ is in $\mathcal{R}, \mathcal{RE}, co-\mathcal{RE}$ or in ...
1
vote
2answers
33 views

Prove the halting problem is undecidable using Rice's theorem

Is it possible to prove that the Halting problem is undecidable using Rice's theorem? Here's what I've tried and failed: We want to reduce Rice's Theorem (decide if a language has the nontrivial ...
0
votes
1answer
78 views

Decidability of the TM's computing a none empty subset of total functions

I have this HW problem: Let $F$ be the set of computable total functions, and let $\emptyset\subsetneq S\subseteq F$. Denote $$L_S=\{ \langle M \rangle | M \text{ is a TM that computes a function ...
0
votes
1answer
23 views

Are all functions with constant space complexity in $REG$?

The Wikipedia article about regular languages mentions that $DSPACE(O(1))$ is equal to $REG$. Can I conclude from this that every function in $R$ with constant space complexity is in $REG$?
2
votes
1answer
70 views
+50

a theorem about the enumeration of R and a subset of always halting TMs

The question: Let $L_1,L_2,...$ be an enumeration of $\mathcal{R}$ and define $A_i = \{\langle M\rangle \ | \ L(M) = L_i\}$. Let $L$ be a language in $\mathcal{RE}$ such that $L \subset \{\langle ...
1
vote
0answers
41 views

Is $f$ which returns the $n$-th word in $\overline{H_{TM,\epsilon}}$ computable?

The question itself: Let $f:\mathbb{N}\to\Sigma^\star$ be such that $f(n)$ returns the $n$-th word in $\overline{H_{TM,\epsilon}}$ (which is the complement of the language of TMs which accept ...
5
votes
1answer
19 views

Primitive Recursion equipped with an evaluator function

The wikipedia article for primitive recursion mentions a limitation that primitive recursive function can't compute the function $ ev(i,j) $ which computes the $ i $th primitive recursive function on ...
3
votes
1answer
36 views

Theoretical justification of “halting problem avoidance”

The wikipedia page for the Halting problem mentioned practical solutions to avoiding the halting problem such as avoiding infinite loops. And there is a mention that "by restricting the capabilities ...
3
votes
1answer
109 views

Undecidable vs Unsolvable?

In decidability theory, I understand that if a problem is labeled "decidable", then we can construct a Turing Machine that definitively tells us whether an input is valid or invalid. My question is ...
1
vote
2answers
152 views

Is it possible to design a programming task that is unsolvable?

Can a problem (described by a set of inputs and accepted answers) be designed such that for all programs which produce an answer in finite time for a (countably) infinite number of inputs, at least ...
1
vote
1answer
89 views

Is the system of measuring length in the US is Turing complete?

The author here writes: Little known fact, the system of measuring length in the US is Turing complete My question is: Is the system of measuring length in the US is Turing complete?
3
votes
1answer
57 views

Undecidability of REGULAR_TM (Detail within Proof)

I'm reading through Sipser's Intro to the Theory of Computation for a class, and I'm having trouble understanding one of the examples in the book. The example shows how $REGULAR_{TM}$, defined as the ...
3
votes
2answers
58 views

Given a r.e. (recursively enumerable) language, L, how many Turing machines semi-decide L?

$L\subseteq \{0,1\}^*$ Since the language is r.e. there is definitely at least one Turing Machine that semi-decides the language. I'm thinking that if you have one Turing Machine that semi-decides ...
2
votes
2answers
61 views

Language of TMs such that one state is visited most often

To be safe, let me start this question by giving the definition of a TM I will be using: A TM is some $M = (Q, \Sigma, \Gamma, q_0, \delta, q_F)$, where $Q$ is the finite state set, $\Sigma \subset ...
0
votes
1answer
44 views

Showing a language is context free. Use PDA or CFG?

I am wondering on how to approach a specific problem I am struggling with. I am not understanding which way to approach it and how to solve it. Show language $L$ is context free, where $L = ...
1
vote
0answers
46 views

Language of Turing machines that never visit some given state

Can someone help me to determine and prove if the following language is decidable or not? I tried to think on some reductions but I can't figure it out... $$A=\{\langle M\rangle|\text{$M$ is $TM$ ...
1
vote
2answers
35 views

The language of Turing machines that accept exactly $k$ inputs

For a fixed $k\geq 0$, let $X_k = \{\langle M\rangle\mid |L(M)|=k\}$, where $\langle M\rangle$ is the encoding of a Turing machine $M$ and $L(M)$ is the language $M$ accepts. Is $X_k$ ...
8
votes
1answer
68 views

Church-Turing and physical PDEs

When I read about the Church-Turing thesis it seems to be a common claim that "physical reality is Turing-computable." What is the basis for this claim? Are there any theoretical results along these ...
3
votes
1answer
20 views

How to identify strongly confluent cellular automatas?

Lets represent a class of cellular automata as a finite, unidimensional bit array state : [Bit], plus a rewrite rule ...
0
votes
1answer
54 views

Implications of Halting Problem being unsolvable?

I came across a confusing situation when reducing the Halting Problem (HP) to the Blank Tape Accepting Problem (BP). We know that since HP can be reduced to BP, BP is decidable $\implies$ HP is ...
1
vote
1answer
34 views

Prove Undecidability Without Using Rice's Theorem

Show that checking if a TM accepts some input string of length greater than some constant $k$ is undecidable. Here the constant $k$ is publicly known. I tried solving this problem by trying to reduce ...
1
vote
1answer
27 views

Turing Machine that always returns a blank tape

Is it possible to construct a Turing Machine such that given any finite input on a tape $s$, it clears the tape in a finite amount of time? I have used such a TM as an intermediate step to show a ...
0
votes
1answer
44 views

If the strings of a language can be enumerated in lexicographic order, is it recursive?

If the strings of a language L can be effectively enumerated in lexicographic order then is the statement "L is recursive but not necessarily context free" is true?
-1
votes
1answer
61 views

How do you know a problems is non-computable?

I am currently looking at intractable problems and N/NP etc but am a little confused about one term used in the book I am reading. It says in this book that a non computable problem is one which ...
-1
votes
1answer
65 views

How can a Turing machine accept infinite number of inputs? [closed]

How it is possible for a turing machine to process an infinitely long input ?
1
vote
4answers
205 views

Complexity analysis of an unsolvable algorithmic problem?

In my automata theory class, for our term project we are required to present a complexity analysis for our algorithmic problem. I have chosen an unsolvable problem, and he has off-the-cuff mentioned ...
3
votes
1answer
102 views

Whatever that can be done using algorithm can be done using Turing machine

In 1937 how was Alan Turing so sure that all that can be done using algorithms can be implemented using a Turing machine? Since that period many new algorithms were implemented. What was his ...
0
votes
1answer
98 views

Prove whether this problem is decidable or undecidable [duplicate]

So I am reviewing my notes for this problem, and I cant seem to understand how this problem works. Say we have M, and M accepts an input that makes it visit every non-halting state. I convinced ...
0
votes
0answers
42 views

Does Turing Completeness imply the existence of a Universal Program?

Please correct me if at any time my definitions are wrong. Suppose we have a programming language $L$ over some set $D$ with semantic (partial) n-ary functions $\varphi^n:D \to (D^n \to D)$. Assume $L ...
0
votes
1answer
36 views

If $A$ is m-complete for $\Sigma_n$, is $\overline{A}$ m-complete for $\Pi_n$?

If we have a set $A$ that is m-complete for $\Sigma_n$, then is it's complement $\overline{A}$ m-complete for $\Pi_n$? I know that $\overline{A} \in \Pi_n$, but does it inherit the completeness? I ...
5
votes
2answers
101 views

Recommendations for a good (rigorous) text to study Computational Complexity.

I look for a good text to learn basics of computational complexity. I've read some parts of the first two chapters of "Computational Complexity: A Modern Approach" by Boaz Barak and Sanjeev Arora, ...
0
votes
1answer
50 views

Axioms - proof of halt

I am new to this forum and this is my first post. I am interested in solving a problem, but cannot find the way to think about it. If anyone can guide me through it, I would be obliged: Let F be some ...
7
votes
2answers
1k views

Is it possible that the halting problem is solvable for all input except the machine's code?

This question occurred to me about the halting problem and I couldn't find a good answer online, wondering if someone can help. Is it possible that the halting problem is decidable for any TM on any ...
2
votes
1answer
50 views

Recursively enumerable but non recursive subset of an infinte recursive language

How can we show that, for every infinite recursive language, it has a subset that is recursively enumerable but not recursive? I think we need to show there's a list of natural numbers that can't be ...
2
votes
3answers
62 views

Proof that whether a regular language is finite is decidable

I have this question for a homework. The question stems from the fact that you can determine whether a regular language is empty by using a Turing machine to count the states n in the given FSM. When ...
0
votes
0answers
19 views

turing machine decidability language

I must show that this language is decidable but I think it's not {D, Ρ} | D is a DFA and P is a ΡDA which L(D) ∩ L(Ρ) = ∅ } Here what I think I give a reduction from E(TM). I suppose that this ...
1
vote
1answer
55 views

context sensitive language finite or infinite

let L be a CSL. (my understanding/ memory/ expectation is) the problem is L finite or infinite? is undecidable. where was this 1st proved/ published? are there any cases in the literature of ...
26
votes
4answers
5k views

Theoretical machines which are more powerful than Turing machines

Are there any theoretical machines which exceed Turing machines capability in at least some areas?
1
vote
2answers
89 views

Can one consider living (biological) cell to be Turing Complete?

Universal Turing Machine can be boiled down to two components. Infinite tape of input and an action table, a finite state machine that moves read/write head along the tape and writes to it depending ...
3
votes
1answer
48 views

Decidability of equivalence problem with limit

I already know, that the language $$L_0 = \{m \mid \text{the Turing machine $m$ does not stop on an empty tape}\}$$ is not decidable. If I want to know, if $$EQ = \{\langle m, n \rangle \mid L(m) = ...
4
votes
1answer
57 views

Is it decidable whether a linear language contains a square?

A square is a word of the form $ww$. A linear grammar is a CFG that has productions of the form $A\to uBv$ or $A\to u$ (with lower case symbols corresponding to terminal strings). Question: Is it ...
3
votes
2answers
49 views

Showing that the number of primitive-recursion programs for each function is countably-infinite

Problem Statement Prove that if a function $f$ is primitive recursive, then there are countably infinite number of primitive recursive definitions of $f$ Yes, this is a homework question. My ...
2
votes
2answers
118 views

How do I prove that all primitive recursive functions are computable?

I stumbled across an exam question, and I am not sure how to prove that that all primitive recursive functions are computable. Is there a formal definition of this?
0
votes
1answer
25 views

How to prove that the decidable languages are closed against iteration only by enumerators?

We have the $L\in R$, how can we prove that $L^*\in R$ only by enumerators? I try to use induction, but as I understand I wrong... I'd like to get any help!
0
votes
0answers
146 views

Trying to show if two languages are recognizable or not

I have two languages that I am trying to prove are recognizable or not: Let L1 = {<\M, w> : M is a Turing machine that accepts string w and does not accept string ε}. Is L1 recognizable? Prove ...
2
votes
1answer
33 views

Prove that the Kolmogorov complexity function cannot be approached from below

How would one go about proving that Kolmogorov function $K(x)$ cannot be approached from below by any computable function? After some research it seems I must show the function $K(x)$ is not lower ...
3
votes
2answers
121 views

Why classification represents all computations?

I'm a computer science student taking a theory of computation class. Recently we were taught about what is computable and what is not and about the Turing machine. As I understood (please correct me ...
-1
votes
1answer
135 views

Does Every Recognizable language has a subset not Recognizable?

Does every Turing Recognizable language has a subset which is not turing recognizable? i can give some examples but can't prove in general