# Questions tagged [computability]

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

1,528 questions
Filter by
Sorted by
Tagged with
15 views

### What computational model supports arbitrarily sized integers?

I want to do some research, but I don't think it's important the number of bits it takes to represent the integer input and arithmetic on the abstract machine. So what is the model that addresses ...
27 views

### Union of a decidable language with complement of a recursively enumerable language

So the question wants to prove or disprove that 'a Union of a decidable/recursive(i understand them to be the same) language and the complement of a recursively enumerable language is a recursive/...
28 views

### Can a computable program have an infinite output?

Can a computable program produce an infinite output from its (presumably finite) input? *I wouldn't think so for similar argument as to why it can't compute over an infinite input. A follow on (...
21 views

### if there is no reduction from A to B

I'm facing the following question : If there is no $𝐴\leq_𝑚𝐵$ reduction, does this necessarily mean that A is not decidable? for any choice of B. thanks in advance.
94 views

### Undecidability of language involving two TMs

I am currently browsing the lecture notes on computability/decidability and I have encountered the following exercise I am unable to solve. Given $M_1$, $M_2$ Turing machines, is it true that for ...
24 views

### Use the Rice's theorem to prove that the following property of a Recursive Enumerable language L is undecidable

This exercise was taken from the book "Languages and Machines: An Introduction to the Theory of Computation" by Thomas Sudkamp. It refers to exercise 12 (b) chapter 12. Given a language L which is ...
98 views

### Compare two complexity functions having the same asymptotic complexity

For a certain problem two solution algorithms (A1 and A2) with the following execution times have been found: $A1: T_{A1}(n)=4n^2 +7log(n^2)$ $A2: T_{A2}(n) = 4T(n/2) + log(n)$ Say, technically ...
16 views

### Proof by reduction that the Universal Language is not recursive using the complement of the Diagonalization language

I have the following proof which I don't fully understand. L D/ is the complement of the Diagonalizaton Language. L U is the Universal language. Assume U* is a TM for Lu which always halts. ...
35 views

### Are Turing unrecognizable and undecidable languages, recognized and decided by hyper computation?

Do the hyper computing machines/models that are supposed to be more powerful than Turing machines, capable of recognizing and deciding the languages that are not recognizable/decidable by Turing ...
25 views

### In the reduction from HALT to ALLHALT, why does the constructed Turing machine loop indefinitely when the inputted Turing machine rejects?

Let HALT be the language $\{\langle M, w\rangle : M\text{ is a TM that halts on }w \}$. Let ALLHALT be the language $\{\langle M\rangle : M\text{ is a TM that halts on all inputs}\}$. Use a reduction ...
11 views

### Do $PR/Poly$ solve the halting problem of Turing Machine?

I know that $R/Poly$ solves the halting problem, as we can have the program that runs for longest time as advice and check which halts earlier. But what if we weaken the $R$ into something, like $PR$?
28 views

### Would models of computation in other conceivable universes be Turing complete?

I'm interested in gathering some references that discuss the topic of the relationship between computation and physics. Specifically, I'm interested in investigating two points of view: our current ...
65 views

### Can a subset of indexes of a partial recursive function be recursively enumerable but not recursive?

Consider a Gödelian numbering of partial recursive functions. Consider the set of indexes corresponding to some function $\phi$. It may be seen that this set is not recursively enumerable. Does this ...
88 views

### Grammar with fewest variables

I am looking over a past exam for a theory of computation class I am taking, and unfortunately no solutions are provided. I am stuck on this question, and would greatly appreciate any help or hints. ...
14 views

### Is checking if the length of a C program that can generate a string is less than a given number decidable?

I was given this question: Komplexity(S) is the length of the smallest C program that generates the string S as an output. Is the question "Komplexity(S) < K" decidable? With respect to ...