About: Computable function   Sponge Permalink

An Entity of Type : owl:Thing, within Data Space : 134.155.108.49:8890 associated with source dataset(s)

Suppose we have a two-color Turing machine \(T\). Given a positive integer \(n\), we set the tape to be blank except for \(n\) consecutive ones with the leftmost one at the position of the TM head. We simulate the Turing machine, and one of the following happens: * It halts with \(m \in \mathbb{N}\) consecutive ones on the tape, with the head positioned on the leftmost one. In this case we say that \(T\) outputs \(m\) given input \(n\). * It halts, but it does not have the configuration described above. * It does not halt.

AttributesValues
rdfs:label
  • Computable function
rdfs:comment
  • Suppose we have a two-color Turing machine \(T\). Given a positive integer \(n\), we set the tape to be blank except for \(n\) consecutive ones with the leftmost one at the position of the TM head. We simulate the Turing machine, and one of the following happens: * It halts with \(m \in \mathbb{N}\) consecutive ones on the tape, with the head positioned on the leftmost one. In this case we say that \(T\) outputs \(m\) given input \(n\). * It halts, but it does not have the configuration described above. * It does not halt.
sameAs
dcterms:subject
dbkwik:googology/p...iPageUsesTemplate
abstract
  • Suppose we have a two-color Turing machine \(T\). Given a positive integer \(n\), we set the tape to be blank except for \(n\) consecutive ones with the leftmost one at the position of the TM head. We simulate the Turing machine, and one of the following happens: * It halts with \(m \in \mathbb{N}\) consecutive ones on the tape, with the head positioned on the leftmost one. In this case we say that \(T\) outputs \(m\) given input \(n\). * It halts, but it does not have the configuration described above. * It does not halt. Let \(f\) be the set of all ordered pairs \((m,n)\) for which \(T\) outputs \(m\) given input \(n\). We can see that \(f\) is a partial function with domain space and codomain \(\mathbb{N}\). We say that \(T\) computes \(f\), and a partial computable function (or partial recursive function) is a partial function for which there exists a Turing machine that computes it. A computable function (or recursive function) is a partial computable function that is total. That is, a computable function is a function that can be computed with a Turing machine. A function \(f: \mathbb{N} \mapsto \mathbb{N}\) which is not computable is called uncomputable. An uncomputable function may (euphemistically) refer to an uncomputably fast-growing function. There exist functions that eventually dominates all computable functions, the most famous example being the busy beaver function. Such functions are necessarily uncomputable, and grow exceptionally fast, above the order of \(\omega_1^ ext{CK}\) of the FGH. It is important to note that not all uncomputable functions have this property - an example would be the function \(h(n)\) defined as \(1\) if the \(n\)th (in some fixed ordering) Turing machine halts, and \(0\) otherwise. Almost all functions over the natural numbers are uncomputable — there are countably many computable functions and uncountably many functions over the natural numbers.
Alternative Linked Data Views: ODE     Raw Data in: CXML | CSV | RDF ( N-Triples N3/Turtle JSON XML ) | OData ( Atom JSON ) | Microdata ( JSON HTML) | JSON-LD    About   
This material is Open Knowledge   W3C Semantic Web Technology [RDF Data] Valid XHTML + RDFa
OpenLink Virtuoso version 07.20.3217, on Linux (x86_64-pc-linux-gnu), Standard Edition
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2012 OpenLink Software