Timeline for single circuit simulating multiple Turing machines
Current License: CC BY-SA 4.0
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 24, 2020 at 15:32 | comment | added | DeeDee | apologies, let me rephrase -- restricted to inputs of size n, can a circuit simulate two Turing machines that differ on at least one output given same input of size n? and if both TMs are PTIME can the circuit do this in PSZIE? what about as the number of Turing machines grows to 2-4-16... exponentially but remain PTIME is there still a PSIZE circuit that can take care of them? Thanks! | |
| Nov 24, 2020 at 15:19 | vote | accept | DeeDee | ||
| Nov 24, 2020 at 13:46 | history | answered | Luke Mathieson | CC BY-SA 4.0 |