Friedberg–Muchnik theorem
id:
friedberg-muchnik-theorem-283-3791317
title:
Friedberg–Muchnik theorem
text:
In mathematical logic, the Friedberg–Muchnik theorem is a theorem about Turing reductions that was proven independently by Albert Muchnik and Richard Friedberg in the middle of the 1950s. It is a more general view of the Kleene–Post theorem. The Kleene–Post theorem states that there exist incomparable languages A and B below K. The Friedberg–Muchnik theorem states that there exist incomparable, computably enumerable languages A and B. Incomparable meaning that there does not exist a Turing reduc
brand slug:
wiki
category slug:
encyclopedia
description:
original url:
https://en.wikipedia.org/wiki/Friedberg%E2%80%93Muchnik_theorem
date created:
date modified:
2023-08-21T08:54:52Z
main entity:
{"identifier":"Q111982312","url":"https://www.wikidata.org/entity/Q111982312"}
image:
fields total:
13
integrity:
13