Questions tagged [computability]

Computability theory a.k.a. recursion theory.

Filter by
Sorted by
Tagged with
0
votes
0answers
12 views

Power of Multi Tape and Multi Track Turing Machine

How can we prove that the computational power of Multi Track and Multi Tape Turing Machine is same as the Normal or Standard ( One Tape- One Track- One Head) Turing Machine?
1
vote
0answers
97 views

Functional abbreviation for Inst expression in Turing's 1936 paper

In Turing's 1936 paper "On Computable Numbers", For a Turing Machine $M$, $Inst(q_i S_j S_k L q_l ) $ means that if $M$ scans symbol $S_j $ under $m-configuration$ $q_i$, then the symbol ...
-1
votes
1answer
103 views

Are all computable functions monoidal from a category theory POV? [closed]

I have been studying some category theory only to understand the "why" behind the various categorical constructs we use ("borrow") in the world of functional programming. One of ...
11
votes
1answer
166 views

Is there a language of first-order logic such that every r.e. set is Turing-equivalent to some finitely axiomatizable theory in that language?

I hope that mathematical logic / recursion theory type questions are welcome here. I am sorry this question is so long and technical, but I believe that if you read it you will find that it is well-...
1
vote
1answer
141 views

How come Wikipedia says that Random Turing Machines can provide uncomputable output?

Wikipedia article mentioned : Hypercomputation The third paragraph starts off with: Technically, the output of a random Turing machine is uncomputable; however, most hypercomputing literature focuses ...
1
vote
1answer
118 views

What kind of computational model is the brain? [duplicate]

I was wondering what kind of computational model is the human brain (as it seems superior to a Turing machine). Another thing that should be a separate question, What would be a perfect computer model ...
12
votes
2answers
367 views

Complexity relative to the graph of the Busy-Beaver function

This question is inspired by the comments made on this other question that I asked, and by an attempt to provide an explicit example of a complexity question beyond the Turing degree $\mathbf{0}$. (...
5
votes
0answers
176 views

Has there been any development of complexity theory for other Turing degrees than 0?

(I'm not sure if this question is better suited for MathOverflow or here. I'll try here first, and move over to MO later if it appears to be more appropriate.) Complexity theory can be very broadly ...
1
vote
0answers
50 views

Given a program specification, S, what can be said about the size and efficiency of programs that exactly satsify S, with respect to the size of S?

Suppose we are given a program specification, $S$, and we want to reason about programs $P$ that satisfy $S$. One might like to think that if the specification is 'simple', the the program should be '...
1
vote
0answers
78 views

Logic of learning

Does Robust logic (Leslie Valiant), Default logic (Raymond Reiter) and Circumscription logic (John McCarthy) have any relation? I was Mathematician and Computer Science (dual degree undergraduate) ...
-2
votes
1answer
69 views

Definition of Omega Jump [closed]

In the book Computability theory (Rebecca Weber) I stumbled about Exercise 7.1.24 with the definition of the omega jump. The book says: The omega jump of $A$, $A^{(\omega)}$ is the join of all $A^{(n)}...
1
vote
0answers
29 views

Non Turing-Complete Models, Conditional-Complete function?

I know well the distinction between the class of Partial Recursive Functions, and $\mu$-Recursive, i.e. the latter is Turing Complete and the former is equivalent to the LOOP-Program model of ...
0
votes
0answers
79 views

Apredictable sets

Some strange recursion-theoretic notions I encountered, I am unable to make much sense out of them. Some concrete questions below, but I'm also interested in just connections to existing recursion ...
-3
votes
1answer
100 views

Is this a good definition of computability? [closed]

I still haven't found a good definition of computability. All the definitions are either too vague, or they delegate the definition to another loaded term like "anything that uses math to solve a ...
1
vote
1answer
141 views

Extended Church's thesis and internal parametricity

I am wondering if there is any known relationship between these 2 concepts in intensional MLTT as formulated here. Does $Internal\ parametricity \implies ECT$ hold? For forumlation of ECT see https://...
0
votes
2answers
161 views

Is the decidability of a language decidable? [closed]

Is there a Turing machine that takes a language as input and decides/semi-decides if it is a decidable language? Comments + answer say trivially the answer is yes; however, I'm wondering here would ...
0
votes
2answers
151 views

Turing meta-oracle

Let H(P) be some program that given P('s source code) computes whether or not P terminates, i.e. solves the halting problem. H only needs to terminate if P terminates. (This disallows solutions like ...
1
vote
0answers
45 views

Is there an alternative technique to define computable functions other than their definition on natural numbers? [closed]

I am not completely sure that why computable functions is defined as a subset of all functions from/to Natural Numbers, but as far as I know, computation comes from real (physical) world so ...
5
votes
0answers
80 views

Are there languages require many variables to achieve $\Sigma_n^0$ completeness?

The proof of Post's Theorem that I am familiar with assumes you have access to as many variables as you wish in your language. Matiyasevich's Theorem by contrast gives a $\Sigma_n^0$-complete formula ...
-1
votes
1answer
127 views

Gödel-Numbering of the Context-Sensitive Languages

I would like to have a Gödel-numbering of the context-sensitive languages. Because there is no obvious syntactic distinction between LBAs and TMs, I cannot number the former in an immediate way. So I ...
7
votes
1answer
246 views

Uniform mortality problem for Turing Machines

Consider the following generalisation of the mortality problem for Turing Machines. Given a Turing Machine $M$. Is there a bound $k_M$ such that starting from any configuration $c$ machine $M$ ...
3
votes
2answers
169 views

Compactness of domino tilings

I've read in Lemma 2 of the paper 1 that if every square region of the plane admits a tiling, then the whole plain admits a tiling, but the proof is omitted. This sounds like a compactness property, ...
2
votes
0answers
80 views

how is time complexity defined in computational learning theory

In general, when we say an algorithm $A$ PAC learns $C$ in time $t$, we say $A$ takes time $t$ before outputting a hypothesis $h$, and the hypothesis can be evaluated (on every $x$) in time $t$. Now ...
0
votes
1answer
150 views

Why does the Placid Platypus function grow faster than any computable function?

I came across the Placid Platypus function $PP(n)$ today, defined as the minimal number of states needed for a turing machine that prints a string of $n$ ones and halts. This function is claimed to (...
6
votes
1answer
307 views

Is a binary sequence computable iff the Kolmogorov complexity of its initial segments is bounded?

Disclaimer: I am mostly unfamiliar with theoretical computer science, making it hard for me to navigate literature in the field. I ask the following out of curiosity. Background/Motivation: Coming ...
5
votes
1answer
177 views

Minimal information needed for determine some function

From calculus, we know that if someone has a continuous function $f$, it is enough to know $f$'s values on the rationals in order to know $f$ on the entire line. In some sense, a "countable amount of ...
1
vote
0answers
152 views

Solving the Halting problem for most inputs [closed]

Is it possible to solve the following version of the Halting problem : given any Turing machine and some input tape, the program should answer if this pair halts or not except possibly for one Turing ...
11
votes
0answers
163 views

Can two-tape read-only Turing machines recognize any recursive language?

Suppose that a $k$-tape read-only Turing machine receives its input on each $k$ tapes. It cannot write on the tapes, but it can move on them in both ways, even move off from the input. So for example, ...
6
votes
2answers
280 views

Algorithm for identifying unprovable statements

I understand that this may depend on the specific set of axioms, but is there a general way (algorithm) for automatically detecting unprovable statements within a set of axioms? For example: If there ...
2
votes
1answer
174 views

Is there a difference between incompleteness and unknowable? [closed]

Godel proved that there are statements that are true but not provable. Unproven conjectures such "Twin Primes" might fall into such a class, as I understand. If so, does it mean that we will never ...
6
votes
3answers
229 views

Why/when do we ever need transfinite loop variants?

I do not understand why one would ever need a transfinite loop variant. Why do natural-number-valued variants not suffice? My simple (but perhaps too naive) argument is: if a loop $L$ terminates ...
5
votes
1answer
295 views

Is there a useful notion of being “approximately computable”

It seems that we can define a notion of being “approximately computable” where a set, $S$, is approximately computable if there is a family of computable functions $f_n(x)$ such that $$\lim_{n\to\...
11
votes
1answer
542 views

Non-comparable natural numbers

The "name the biggest number game" asks two players to write down a number secretly, and the winner is the person who wrote down the larger number. The game commonly allows players to write down ...
5
votes
1answer
182 views

Complexity of type-checking in relation to complexity of normalization

In order to verify that a terminating program terminates, one thing that can be done is to actually run the program. That may take a lot of time. If the program is typed in a total type-system, we can ...
4
votes
4answers
259 views

Reference request: Arithmetic circuit complexity

I am completely new to this field. I want to read the prelims and unfortunately, I don't see any book written for a beginner in this area. Can anyone give me some basic starting points/references(text/...
-1
votes
2answers
752 views

Are these problems in NP class?

${\bf New\ version}$ [Version 1.2] Let $f: \mathbb{N} \to \{0,1\}$ be a computable function, ${\bf Fin}(\mathbb{Z})$ be the set of all finite subsets of $\mathbb{Z}$, and $W: {\bf Fin}(\mathbb{Z}) \...
6
votes
2answers
763 views

a polynomial representation of boolean functions

I came up with this linear transformation to map boolean functions to polynomials and it seems to have some nice properties. I was wondering if there is any reference describing this (and/or similar) ...
1
vote
2answers
238 views

Is true randomness and the physical Church-Turing thesis incompatible?

As follow up to Does the physical Church-Turing thesis imply that all physical constants are computable?, I ask if true randomness (as predicted by QM) and the physical Church-Turing thesis are ...
3
votes
2answers
355 views

Does the physical Church-Turing thesis imply that all physical constants are computable?

The physical Church Turing thesis is a conjecture that any physically computable algorithm can be computed by a Turing machine. Let us create a machine that, for example, outputs the digits of the ...
-5
votes
1answer
140 views

Are there proofs which show that AIs are bound to be “worse” than the human brain? [closed]

I was talking with two PhDs (both teach IT related subjects) about artificial intelligence the other day. They were in agreement that an AI can never reach the level of the human brain, but failed to ...
4
votes
2answers
850 views

Enumerating decidable languages

[The assumption in this question is wrong. It is possible to enumerate exactly the decidable languages with semideciders.] Lets say we have a TM $M_E$ enumerator that writes out codes of TM's on a ...
10
votes
4answers
491 views

Is there a notion of computability on sets other than the natural numbers?

Is there a notion of computability on sets other than the natural numbers? For the sake of argument, let's say on sets $S$ that biject with $\mathbb{N}$. It's tempting to say "yes, they are ...
3
votes
0answers
32 views

references for optimal computation under memory constraint?

Can someone help me find some references for finding good execution schedule given memory constraint? Assuming computation graph is simple in some sense (ie, small tree-width) There is this reference ...
8
votes
4answers
481 views

Impossibility in Computability and Complexity: always ultimately due to diagonal arguments?

In Computability, if we want to prove that a problem is not recursive or not recursively enumerable, we can use e.g. reductions from other non-recursive or non-r.e. problems, Rice's theorem, Rice-...
6
votes
1answer
863 views

Show that minimal CFG is undecidable via mapping reduction

Actually the problem below is an exercise in Sipser's textbook (Problem 5.36). However, from my perspective, it is not so trivial so that I post this question on this site instead of CS.SE. The ...
14
votes
0answers
274 views

Computability of a “weird” set

The starting point of this question is the observation that the smallest positive integers $a,b,c$ satisfying $$\frac{a}{b+c} + \frac{b}{a+c} + \frac{c}{a+b} = 4$$ are absurdly high. This leads to ...
10
votes
1answer
246 views

Equilibrium in a Halting Game

Consider the following 2-player game: Nature randomly picks a program Each player plays a number in [0, infinity] inclusive in response to nature's move Take the minimum of the players’ numbers, and ...
-1
votes
1answer
88 views

What is the relation between P-immune languages and NP-complete languages? [closed]

Can a NP-complete language be P-immune? Why can't existence of P-immune languages separate NP from P?
1
vote
1answer
112 views

Set of languages that can represent every c. e. languange

Could we find any set of languages $S$, such that it can represent every c. e. languange as it's union, intersection, complement, production(times of element ), and $S\subset X$, where $X\subseteq c.e....
3
votes
1answer
69 views

Can any c.e. language with infinite words be decomposed into infinite CFLs with infinite words?

Suppose $L$ is a computably enumerable language, can it be decompose into infinite CFLs with infinite words ? $$L=\bigcup_{L_i\in CFL }^{\infty}L_i$$ Second question: if it is possible that every $L$...

1
2 3 4 5
7