[WSRP25] Empirical analysis of P vs. NP: on the equivalence of Turing machines as partial functions

michaelsunsd · July 10, 2025, 8:15pm

wolframcommunity · July 22, 2025, 6:32pm

– you have earned Featured Contributor Badge
Your exceptional post has been selected for our editorial column Staff Picks http://wolfr.am/StaffPicks and Your Profile is now distinguished by a Featured Contributor Badge and is displayed on the Featured Contributor Board. Thank you!

michaelsunsd · September 30, 2025, 5:38am

Edited 28 September 2025 where the following notable changes were made:

Compile functions with FunctionCompile to significantly improve runtime
Fix a bug with the pruning step where it would start at a rule shifted forward and remove rules it shouldn’t have
Add significantly more analysis of runtime

Topic		Replies	Views
[WSC17] Exploring Halting Times in Turing Machines Questions ruliology , graphics-and-visualization , wolfram-high-school-summer-research-program	0	15482	July 6, 2017
Mathematical Games: Turing machines Staff Picks ruliology , computer-science , demonstrations , graphics-and-visualization , interface-construction , staff-pick , events-and-media , wolfram-repositories	1	7523	July 19, 2024
[WSRP24] Generating macro machine simulations and proofs of halting for busy beaver Turing machines Staff Picks computer-science , discrete-mathematics , graphics-and-visualization , graphs-and-networks , interface-construction , staff-pick , wolfram-high-school-summer-research-program , mathematics-and-foundations	2	8613	July 24, 2024
[WSC21] Turing machines with longer head-jumps and complexity Staff Picks ruliology , computer-science , graphics-and-visualization , graphs-and-networks , staff-pick , wolfram-high-school-summer-research-program	3	11167	August 29, 2021
[WSRP23] Complex behavior in 2-color 2-state 2D Turing machines Staff Picks computer-science , discrete-mathematics , graphics-and-visualization , interface-construction , statistics-and-probability , staff-pick , wolfram-high-school-summer-research-program	1	8709	July 25, 2023

[WSRP25] Empirical analysis of P vs. NP: on the equivalence of Turing machines as partial functions

Related topics