Gary Wong on Nostr: npub17czt0…lutc6 But if we consider Boolean circuits ("induced subcircuits" of a ...
npub17czt0gwf5lfr6v3fj06teh8tlhvzy8gs4duzg09gex5uxll420mq9lutc6 (npub17cz…utc6) But if we consider Boolean circuits ("induced subcircuits" of a universal directed acyclic graph of Boolean operations), then I guess almost all sufficiently large Boolean circuits perform enough computation that you could attach them to a tape reader/writer to construct a universal Turing machine? And by Rice's theorem, almost all such circuits exhibit undecidable behaviour...
Someone must've thought of that, but I don't know a name for it ("Rado circuit" gives no search hits).
Published at
2024-03-09 01:52:59Event JSON
{
"id": "f2ea7a248a1ca50d1d415dcc318811d34365046e938cd6196aa5329f96894553",
"pubkey": "1acc896728da81ca60805872dde397577d4c07c5a86544f8e323de404b2aa2d4",
"created_at": 1709949179,
"kind": 1,
"tags": [
[
"p",
"f604b7a1c9a7d23d322993f4bcdcebfdd8221d10ab78243ca8c9a9c37ff553f6",
"wss://relay.mostr.pub"
],
[
"p",
"5bc998b96064378cf88a7919bd02db8cfeee50bc5eecef8ea5e33b82b7052a4a",
"wss://relay.mostr.pub"
],
[
"e",
"6f29b473dc7efe4398ffe819f03455c6ed820ec81948f3d85ad50e7ddd2db868",
"wss://relay.mostr.pub",
"reply"
],
[
"proxy",
"https://mastodon.nz/users/gtw/statuses/112063229421779232",
"activitypub"
]
],
"content": "nostr:npub17czt0gwf5lfr6v3fj06teh8tlhvzy8gs4duzg09gex5uxll420mq9lutc6 But if we consider Boolean circuits (\"induced subcircuits\" of a universal directed acyclic graph of Boolean operations), then I guess almost all sufficiently large Boolean circuits perform enough computation that you could attach them to a tape reader/writer to construct a universal Turing machine? And by Rice's theorem, almost all such circuits exhibit undecidable behaviour...\n\nSomeone must've thought of that, but I don't know a name for it (\"Rado circuit\" gives no search hits).",
"sig": "3a07beea8809adf4cb119160c0fd4994c88442387bd7cca368ceaf3ea1343d78454d3e90cf707101c8c4bf17973edd08cb3ea1ff26aac928267c0ecd7451ffaa"
}
