# Questions tagged [computability]

Computability theory a.k.a. recursion theory.

408 questions
Filter by
Sorted by
Tagged with
88 views

### Halting problem with minimal Turing Machine as promised input

Consider the following Turing Machine A. Input: Turing Machine M that recognizes some language L(M) Output: If M is minimal (i.e. its length is minimum among Turing Machines that recognize the same ...
• 49
93 views

### Is any procedure satisified by the principle of least action able to be simulated by Turing Machine?

The Hamilton action $S$ is defined as following: $$S=\int^T_0 L(q,\dot{q})dt$$ the integral along any actual or virtual (conceivable or trial) space-time trajectory q(t) connects two specified space-...
• 1,077
60 views

### Computing non-halting inputs of semantic non-equivalent programs

Let P and Q be two programs take one natural number as input and produce no output and they are not semantically equivalent, that is, there exists at least one input value n such that either P(n) ...
52 views

### Source for the "Recursion Theorem" in the context of Turing Machines

Hi and thank you for reading me, I saw a result that interests me in this lecture by Shalev Ben-David, called the "recursion theorem" (Theorem 19.1). It roughly states that : Fix an input ...
81 views

### When is an upper bound on the longest irreducible program outputting something computable?

This is a repost of this mathoverflow question. Given some way to to encode programs to strings with a finite alphabet, which we assume has a computable translation to/from Turing machines, a program ...
37 views

### Integration of analytic function

It is the continuation of the question: Complexity of analytic functions and integrals. Given an input integer $t$ and a sequence of analytic functions $f_n(\cdots(f_0(x))$, with parameters $t$ itself,...
279 views

1 vote
110 views

### Why does the Time Hierarchy Theorem fail relative to promise problems?

Define Program Evaluation (PE) to be the promise problem of determining whether a program (written in a Turing-complete language) returns True or False. The promise is that the program will return ...
• 528
79 views

### Many-one equivalence of sets that differ finitely

[This is a duplicate of my question from Mathematics Stack Exchange: https://math.stackexchange.com/questions/4792354/many-one-equivalence-of-sets-that-differ-finitely I am posting it here since it ...
• 115
546 views

### Technical limitations of Turing machines due to the input and output encoding of values

Convention: Since I will be asking about some technicalities around Turing machines, it behooves to give a precise definition: say, here, “Turing machine” will stand for a $2$-symbol $1$-tape machine ...
• 851
132 views

### Computational power of probabilistic automata

I am a bit confused about the proper role of probabilistic automata (PA) in the theory of computation. Informally, I can imagine they can accept more than finite automata (FA) as they, for instance, ...
• 151
1 vote
63 views

### Many-one degrees of some particular sets

Let $W_0, W_1, W_2,\dotsc$ be an effective numbering of r.e. sets. Consider sets $\text{Emp}=\{x\mid W_x=\emptyset\}$, $\text{Tot}=\{x\mid W_x=\mathbb{N}\}$ and $S_n=\{x\mid W_x=W_n\}$ (for some fixed ...
• 115
1 vote
175 views

### Decidability of the complexity of decision problems

This might be a question that is related to some of the existent questions on the topic in the title, but I still find some answers either not full, or the topic still slightly different (maybe due to ...
• 111
1 vote
129 views

• 851
301 views

### Is there a well-defined notion of an “R/poly” complexity class?

This would be the complexity class of all problems that are decidable in finite time with a polynomial length advice string that can be arbitrarily hard to compute. But potentially undecidable without ...
• 353
158 views

### What is formal definition of non-deterministic algorithm in context of primitive/general recursion?

I want to understand general method for formally defining non-deterministic algorithm. But all formal definitions I see are related to FSM/Turing-machines. What is the reference for non-deterministic ...
• 315
1 vote
131 views

### Do realizable systems always have some non-well-founded sets?

Suppose we are standing outside a realizable system which admits CZF or a similar constructive set theory. Then consider the following: LEM is not realized (e.g. this MSE answer) The traditional ...
• 271
83 views

### Generalizing Quines: Outputting an Arbitrary Function of Source Code

​​A Quine is a (non-empty) program $P$ that takes no inputs and returns its own source code $\langle P\rangle$ as the only output. For a function $f$ (with appropriate domains and range) define an $f$-...
325 views

### How to prove that a language that allows infinite loops is still not Turing-complete?

CPS translations will always use pairs, either explictly or by currying. Though I can't find a reference for that, I'm assuming this is a necessary condition (I'd appreciate a reference if someone has ...
• 387
60 views

### Input-Output Machines

From what I know, there is a vast literature on language recognizers in computer science. Language recognizers are machines (e.g., Finite State Automata, Pushdown Automata, Turing Machines, ...) that, ...
• 101
137 views

### Reference for "A Turing machine cannot be equipped with an oracle for itself"

Starting with a basic Turing machine, successive applications of the Turing jump produce successively more powerful machines, that can be indexed by any ordinal. A tempting error for students, and one ...
• 846
42 views

### Computability for universal quantum turing machines

I would like to ask if anyone has any ideas about what a universal quantum turing machine (UQTM) can do as supposed to a classical universal turing machine (UTM) (i.e. quantum computer vs classical ...
134 views

### Does Bellantoni-Cook safe recursion (or any other implicit characterization of P) admit Kleene's second recursion theorem?

Abstractly, by a programming language that operates on binary strings I mean a set $P$ of programs along with a semantics relation $[p](x) = y$, the program $p$ on string $x$ halts with output $y$.&...
• 851
1 vote
113 views

### Extension of primitive recursion, that is as powerful as System-T

I know that System-T restricted to first-order types is exactly as powerful as primitive recursive functions, because I proved it in Agda. I asked myself, if there is a extension of primitive ...
1k views

### What happens when the Linz halting problem proof is based on simulation of the input?

Applying a Simulating Halt Decider to the Linz Halting Problem Proof Of course it is obvious that no halt decider H can possibly return a correct halt status for any input defined to do the opposite ...
• 43
63 views

### Are there parsers that can parse languages in more expressive grammars than context-free grammars?

The Earley Parser is able to parse all context-free languages. Are there parsers that can parse say languages in context-sensitive grammars? I realize ambiguous grammars are non-deterministic and ...
• 101
128 views

### Gurevich's theorem on primitive recursive functions being logspace-computable

I recently came across the following result attributed to Gurevich, according to which I understood that the class of problems solvable by primitive recursive functions is precisely the class L of ...
• 1,029
1 vote
61 views

### Generalization of computability to continuous for loops? [closed]

A computable function, formulated in the sense of mu recursion, can compute a for or do loop over some (possibly infinite) integer range. I was wondering if a suitable generalization exists that ...
282 views

### An analogue of Scott continuity for infinite-time-Turing-computable functions

$\newcommand{\tb}{2_{\!\bot}}\newcommand{\tbO}{\tb^{\,\omega}}$Let $2 = \{0,1\}$ and $\tb = \{0,\bot,1\}$. Scott continuity is important for defining models of lambda calculus, a formalism for ...
121 views

### Are there more learnable but undecidable cases except the halting problem

Per request, I cross post the question here which is original from math.stackexchange In the ICML 1996 paper, On the Learnability of the Uncomputables, by Richard Lathrop, he proved that halting ...
• 121
398 views

### What are the application of Scott-Topology in theoretical computer science?

During a work I came across the Scott-Topology and I see that Scott-continuous functions show up in the study of models for lambda calculi. What I cannot understand is how this enrich the lambda-...
• 91
232 views

### Understanding the construction of an uncomputable function

The following is from Arora and Barak's "Computational Complexity." I think one does not have to read the second paragraph of the proof to answer this question. Theorem 1.10 There exists a ...
• 109
159 views

### How can I switch into computability theory when I am part way through my PhD in deep learning?

I am partway through my PhD studying deep learning. I chose it just because it's useful and would yield a lot of industry opportunities. However, I am really missing my previous coursework in ...
• 101
86 views

### Expressive power of lambda-calculus with restricted application

Consider a syntactic restriction of the (untyped) $\lambda$-calculus in which an application cannot have another application as an immediate subterm. More precisely, restricted terms ($R,S,...$) and ...
• 653
247 views

### Why are some classes (ALL, ELEMENTARY, R, etc) badly behaved as oracles?

Some classes, such as ALL, ELEMENTARY, and R, are very badly behaved when used as oracles. For instance, all three of these classes trivially collapse P and EXP, even though (by the Time Hierarchy ...
• 528
124 views

• 505