# Questions tagged [computability]

Computability theory a.k.a. recursion theory.

338 questions
Filter by
Sorted by
Tagged with
580 views

### Validity implies NP=#P? [closed]

Valid progams for NP imply every solution is a valid answer. NP not equals #P implies not all solutions are answers. Therefore, Validity implies NP=#P. NP is the problem class for ...
457 views

### Help proving a 3CNF related prob. is in P

I need help proving that this problem is decidable in polynomial-time: Input: a 3CNF formula with more than one clause. Question: can the formula be divided into two satisfiable 3CNF formulas ? ...
1k views

### Feasibility of Gödel machines

Recently I stumbled upon quite an interesting theoretical construct. A so called Gödel machine It's a general problem solver which is capable of self-optimization. It's suitable for reactive ...
131 views

### Oracle that will provide any computable information about another oracle

Suppose I have an oracle X. Then let Y be an oracle which will answer any computable question about X. In other words, Y takes as input a Turing program which can in turn make calls to X. Y then ...
317 views

997 views

### Transition Diagram of a Universal Turing Machine

I have searched the web for the transition diagram of a universal Turing machine without luck. Is anyone aware of such a diagram? I need this as a reference, so preferably a book or a published ...
6k views

### What's the simplest noncontroversial 2-state universal Turing machine?

I'm wanting to encode a simple Turing machine in the rules of a card game. I'd like to make it a universal Turing machine in order to prove Turing completeness. So far I've created a game state ...
289 views

### Concerning decidability of a problem on real numbers [closed]

This question is an outgrowth of a certain maths problem I've been thinking about. Suppose you use an oracle to represent a real number. The oracle is of the following form: you give it an integer ...
1k views

### Are there decidable problems for which for no algorithm we can give time bounds?

Are there decidable problems such that for no algorithm which solves the problem we can give a time bound as a function of the length n of the input instance? I arrived at this question because I was ...
1k views

### Is the concept of the Turing Machine derived from automata?

I was just recently having a discussion about Turing Machines when I was asked, "Is the Turing Machine derived from automata, or is it the other way around"? I didn't know the answer of course, but I'...
692 views

### Examples of reversible computations

Irreversible computations can be intuitive. For example, it is easy to understand roles of AND, OR, NOT gates and design a system without any intermediate, compilable layer. The gates can be directly ...
217 views

### Halting on a (possibly one-way) write-once tape

Consider Turing machines (with the Busy Beaver "design specifications") that must write a 1 whenever they read a 1 (i.e., "write once"). ${}$1. $\:$ Is the halting problem decidable for these ...
2k views

### Decidability of the halting problem on finite computers [closed]

I've seen two competing and contrary arguments for this problem. One states that real computers are linear-bounded automata, and therefore the halting problem is decidable. The other states that ...
1k views

### Class of functions computable by Coq

Since it does not allow nonterminating computation, Coq is necessarily not Turing-complete. What is the class of functions that Coq can compute? (is there an interesting characterization thereof?)
494 views

273 views

### Is there any work done on developing difference-calculus of Turing Machines (or simpler Formal Languages)

I am attempting to develop some notions of a difference-calculus between a notional Ideal Turing Machine conceived by a developer (e.g. whatever is intended by a software developer), call it $M_I$, ...
741 views

### Is there any proof that a network made of Turing machines can't solve the halting problem? [closed]

My question points to the fact that Turing machines are isolated by definition. But what if they can send and receive information from/to other Turing machines? What if they can be "interrupted" at ...
351 views

### Does $\Sigma(n+1)-\Sigma(n)$ eventually dominate every computable function?

Let $\Sigma$ be Radó's Busy Beaver function, and define $\Delta(n) \ = \ \Sigma(n+1) - \Sigma(n)$ for all $n \in \mathbb{N}$. Question: Does the function $\Delta$ eventually dominate every ...
653 views

### Is halting that hard? [Yes] [closed]

I want to make a modification to the halting problem. The output now has two possibilities: This program halts and it does not have the crossing structure (defined below); This program does not halt ...
2k views

### If an abstract machine can simulate itself, does that make it Turing complete?

For instance, in programming languages it's common to write an X-in-X compiler/interpreter, but on a more general level many known Turing-complete systems can simulate themselves in impressive ways (e....
2k views

### Can chess simulate a Universal Turing Machine?

I am looking to get a definite answer to title question. Is there a set of rules that translates any program into a configuration of finite pieces on an infinite board, such that if black and white ...
355 views

### Hilbert's Tenth Problem and nonrecursive Diophantine sets

In her paper Defining Integers, Alexandra Shlapentokh presents the following as an immediate corollary of the undecidability of Hilbert's Tenth Problem --- that is, the language $\{p : p$ is a ...
677 views

### Computational hardness of “real” computer programs

I have often heard it said that you cannot write a program to catch bugs in a web browser, or word-processor, or operating system, because of Rice's Theorem: any semantical property for a Turing-...
298 views

### Simple model of computation with homoiconicity

Is there a simple model of computation with homoiconicity? It would also be nice if, like beta reduction in lambda calculus, every step in execution yields a new valid program. Besides the lack of ...
855 views

### Complexity of Tensor Rank over an Infinite Field

A tensor is a generalization of vectors and matrices to higher dimensions and the rank of a tensor also generalizes the rank of a matrix. Namely, the rank of a tensor $T$ is the minimum number of rank ...
1k views

### Decidability of equality of CFL's

Following problem is decidable: Given a context-free grammar $G$, is $L(G) = \varnothing$? Following problem is undecidable: Given a context-free grammar $G$, is $L(G) = A^{\ast}$? Is there a ...
Given a set of pairs of words $P = \{(\alpha_1, \beta_1), \dots, (\alpha_n, \beta_n)\} \subseteq \Sigma^*\times\Sigma^*$, the Post Correspondence Problem (PCP) is to decide wether or not there are ...