3 ms·

Cool! Now build it in Turing Complete and export it to an FPGA

deelowe 4y ago
For those wondering: https://store.steampowered.com/app/1444480/Turing_Complete/ https://store.steampowered.com/app/1444480/Turing_Complete/
westurner 4y ago
From KiCad https://en.wikipedia.org/wiki/KiCad https://en.wikipedia.org/wiki/KiCad : > KiCad is a free software suite for electronic design automation (EDA). It facilitates the design and simulation of electronic hardware. It features an integrated environment for schematic capture, PCB layout, manufacturing file viewing, SPICE simulation, and engineering calculation. Tools exist within the package to create bill of materials, artwork, Gerber files, and 3D models of the PCB and its components. https://www.kicad.org/discover/spice/ https://www.kicad.org/discover/spice/ : > KiCad integrates the open source spice simulator ngspice to provide simulation capability in graphical form through integration with the Schematic Editor. PySpice > Examples: https://pyspice.fabrice-salvaire.fr/releases/v1.6/examples/index.html#examples-page https://pyspice.fabrice-salvaire.fr/releases/v1.6/examples/i... : + Diode, Rectifier (AC to DC), Filter, Capacitor, Power Supply, Transformer, [Physical Relay Switche (Open/Closed) -> Vacuum Tube Transistor -> Solid-state [MOSFET,]] Transistor, From the Ngspice User's Manual https://ngspice.sourceforge.io/docs/ngspice-37-manual.pdf https://ngspice.sourceforge.io/docs/ngspice-37-manual.pdf : > Ngspice is a general-purpose circuit simulation program for nonlinear and linear analyses.* > Circuits may contain resistors, capacitors, inductors, mutual inductors, independent or dependent voltage and current sources, loss-less and lossy transmission lines, switches, uniform distributed RC lines, and the five most common semiconductor devices: diodes, BJTs, JFETs, MESFETs, and MOSFETs. > [...] Ngspice has built-in models for the semiconductor devices, and the user need specify only the pertinent model parameter values. [...] New devices can be added to ngspice by several means: behavioral B-, E- or G-sources, the XSPICE code-model interface for C-like device coding, and the ADMS interface based on Verilog-A and XML. Turing completeness: https://en.wikipedia.org/wiki/Turing_completeness https://en.wikipedia.org/wiki/Turing_completeness : > In colloquial usage, the terms "Turing-complete" and "Turing-equivalent" are used to mean that any real-world general-purpose computer or computer language can approximately simulate the computational aspects of any other real-world general-purpose computer or computer language. In real life this leads to the practical concepts of computing virtualization and emulation. [citation needed] > Real computers constructed so far can be functionally analyzed like a single-tape Turing machine (the "tape" corresponding to their memory); thus the associated mathematics can apply by abstracting their operation far enough. However, real computers have limited physical resources, so they are only linear bounded automaton complete. In contrast, a universal computer is defined as a device with a Turing-complete instruction set, infinite memory, and infinite available time. Church–Turing thesis: https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis ... Lamda calculus (Church): https://en.wikipedia.org/wiki/Lambda_calculus https://en.wikipedia.org/wiki/Lambda_calculus HDL: Hardware Description Language > Examples: https://en.wikipedia.org/wiki/Hardware_description_language#Examples_of_HDLs https://en.wikipedia.org/wiki/Hardware_description_language#... HVL: Hardware Verification Language: https://en.wikipedia.org/wiki/Hardware_verification_language https://en.wikipedia.org/wiki/Hardware_verification_language awesome-electronics > Free EDA Packages: https://github.com/kitspace/awesome-electronics#free-eda-packages https://github.com/kitspace/awesome-electronics#free-eda-pac... https://github.com/TM90/awesome-hwd-tools https://github.com/TM90/awesome-hwd-tools EDA: Electronic Design Automation: https://en.wikipedia.org/wiki/Electronic_design_automation https://en.wikipedia.org/wiki/Electronic_design_automation
- westurner 4y ago
  More notes for #Q12: Quantum complexity theory https://en.wikipedia.org/wiki/Quantum_complexity_theory#Background https://en.wikipedia.org/wiki/Quantum_complexity_theory#Back... : > A complexity class is a collection of computational problems that can be solved by a computational model under certain resource constraints. For instance, the complexity class P is defined as the set of problems solvable by a Turing machine in polynomial time. Similarly, quantum complexity classes may be defined using quantum models of computation, such as the quantum circuit model or the equivalent quantum Turing machine. One of the main aims of quantum complexity theory is to find out how these classes relate to classical complexity classes such as P, NP, BPP, and PSPACE. > One of the reasons quantum complexity theory is studied are the implications of quantum computing for the modern Church-Turing thesis. In short the modern Church-Turing thesis states that any computational model can be simulated in polynomial time with a probabilistic Turing machine. [1][2] However, questions around the Church-Turing thesis arise in the context of quantum computing. It is unclear whether the Church-Turing thesis holds for the quantum computation model. There is much evidence that the thesis does not hold. It may not be possible for a probabilistic Turing machine to simulate quantum computation models in polynomial time. [1] > Both quantum computational complexity of functions and classical computational complexity of functions are often expressed with asymptotic notation. Some common forms of asymptotic notion of functions are \Omega(T(n)) and \Theta(T(n)). > \Theta(T(n)) expresses that something is bounded above by cT(n) where c is a constant such that c>0 and T(n) is a function of n, \Omega(T(n)) expresses that something is bounded below by cT(n) where c is a constant such that c>0 and T(n) is a function of n, and \Theta(T(n)) expresses both O(T(n)) and \Omega(T(n)). [3] These notations also their own names. O(T(n)) is called Big O notation, \Omega(T(n)) is called Big Omega notation, and \Theta(T(n)) is called Big Theta notation. Quantum complexity theory > Simulation of quantum circuits https://en.wikipedia.org/wiki/Quantum_complexity_theory#Simulation_of_quantum_circuits https://en.wikipedia.org/wiki/Quantum_complexity_theory#Simu... : > There is no known way to efficiently simulate a quantum computational model with a classical computer. This means that a classical computer cannot simulate a quantum computational model in polynomial time [P]. However, a quantum circuit of S(n) qubits with T(n) quantum gates can be simulated by a classical circuit with O(2^{S(n)}T(n)^{3}) classical gates. [3] This number of classical gates is obtained by determining how many bit operations are necessary to simulate the quantum circuit. In order to do this, first the amplitudes associated with the S(n) qubits must be accounted for. Each of the states of the S(n) qubits can be described by a two-dimensional complex vector, or a state vector. These state vectors can also be described a linear combination of its component vectors with coefficients called amplitudes. These amplitudes are complex numbers which are normalized to one, meaning the sum of the squares of the absolute values of the amplitudes must be one. [3] The entries of the state vector are these amplitudes. Quantum Turing machine: https://en.wikipedia.org/wiki/Quantum_Turing_machine https://en.wikipedia.org/wiki/Quantum_Turing_machine Quantum circuit: https://en.wikipedia.org/wiki/Quantum_circuit https://en.wikipedia.org/wiki/Quantum_circuit Church-Turing-Deutsch principle: https://en.wikipedia.org/wiki/Church%E2%80%93Turing%E2%80%93Deutsch_principle https://en.wikipedia.org/wiki/Church%E2%80%93Turing%E2%80%93... Computational complexity > Quantum computing, Distributed computing: https://en.wikipedia.org/wiki/Computational_complexity#Quantum_computing https://en.wikipedia.org/wiki/Computational_complexity#Quant...

For those wondering: https://store.steampowered.com/app/1444480/Turing_Complete/ https://store.steampowered.com/app/1444480/Turing_Complete/

westurner 4y ago

From KiCad https://en.wikipedia.org/wiki/KiCad https://en.wikipedia.org/wiki/KiCad : > KiCad is a free software suite for electronic design automation (EDA). It facilitates the design and simulation of electronic hardware. It features an integrated environment for schematic capture, PCB layout, manufacturing file viewing, SPICE simulation, and engineering calculation. Tools exist within the package to create bill of materials, artwork, Gerber files, and 3D models of the PCB and its components. https://www.kicad.org/discover/spice/ https://www.kicad.org/discover/spice/ : > KiCad integrates the open source spice simulator ngspice to provide simulation capability in graphical form through integration with the Schematic Editor. PySpice > Examples: https://pyspice.fabrice-salvaire.fr/releases/v1.6/examples/index.html#examples-page https://pyspice.fabrice-salvaire.fr/releases/v1.6/examples/i... : + Diode, Rectifier (AC to DC), Filter, Capacitor, Power Supply, Transformer, [Physical Relay Switche (Open/Closed) -> Vacuum Tube Transistor -> Solid-state [MOSFET,]] Transistor, From the Ngspice User's Manual https://ngspice.sourceforge.io/docs/ngspice-37-manual.pdf https://ngspice.sourceforge.io/docs/ngspice-37-manual.pdf : > Ngspice is a general-purpose circuit simulation program for nonlinear and linear analyses.* > Circuits may contain resistors, capacitors, inductors, mutual inductors, independent or dependent voltage and current sources, loss-less and lossy transmission lines, switches, uniform distributed RC lines, and the five most common semiconductor devices: diodes, BJTs, JFETs, MESFETs, and MOSFETs. > [...] Ngspice has built-in models for the semiconductor devices, and the user need specify only the pertinent model parameter values. [...] New devices can be added to ngspice by several means: behavioral B-, E- or G-sources, the XSPICE code-model interface for C-like device coding, and the ADMS interface based on Verilog-A and XML. Turing completeness: https://en.wikipedia.org/wiki/Turing_completeness https://en.wikipedia.org/wiki/Turing_completeness : > In colloquial usage, the terms "Turing-complete" and "Turing-equivalent" are used to mean that any real-world general-purpose computer or computer language can approximately simulate the computational aspects of any other real-world general-purpose computer or computer language. In real life this leads to the practical concepts of computing virtualization and emulation. [citation needed] > Real computers constructed so far can be functionally analyzed like a single-tape Turing machine (the "tape" corresponding to their memory); thus the associated mathematics can apply by abstracting their operation far enough. However, real computers have limited physical resources, so they are only linear bounded automaton complete. In contrast, a universal computer is defined as a device with a Turing-complete instruction set, infinite memory, and infinite available time. Church–Turing thesis: https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis ... Lamda calculus (Church): https://en.wikipedia.org/wiki/Lambda_calculus https://en.wikipedia.org/wiki/Lambda_calculus HDL: Hardware Description Language > Examples: https://en.wikipedia.org/wiki/Hardware_description_language#Examples_of_HDLs https://en.wikipedia.org/wiki/Hardware_description_language#... HVL: Hardware Verification Language: https://en.wikipedia.org/wiki/Hardware_verification_language https://en.wikipedia.org/wiki/Hardware_verification_language awesome-electronics > Free EDA Packages: https://github.com/kitspace/awesome-electronics#free-eda-packages https://github.com/kitspace/awesome-electronics#free-eda-pac... https://github.com/TM90/awesome-hwd-tools https://github.com/TM90/awesome-hwd-tools EDA: Electronic Design Automation: https://en.wikipedia.org/wiki/Electronic_design_automation https://en.wikipedia.org/wiki/Electronic_design_automation

westurner 4y ago
More notes for #Q12: Quantum complexity theory https://en.wikipedia.org/wiki/Quantum_complexity_theory#Background https://en.wikipedia.org/wiki/Quantum_complexity_theory#Back... : > A complexity class is a collection of computational problems that can be solved by a computational model under certain resource constraints. For instance, the complexity class P is defined as the set of problems solvable by a Turing machine in polynomial time. Similarly, quantum complexity classes may be defined using quantum models of computation, such as the quantum circuit model or the equivalent quantum Turing machine. One of the main aims of quantum complexity theory is to find out how these classes relate to classical complexity classes such as P, NP, BPP, and PSPACE. > One of the reasons quantum complexity theory is studied are the implications of quantum computing for the modern Church-Turing thesis. In short the modern Church-Turing thesis states that any computational model can be simulated in polynomial time with a probabilistic Turing machine. [1][2] However, questions around the Church-Turing thesis arise in the context of quantum computing. It is unclear whether the Church-Turing thesis holds for the quantum computation model. There is much evidence that the thesis does not hold. It may not be possible for a probabilistic Turing machine to simulate quantum computation models in polynomial time. [1] > Both quantum computational complexity of functions and classical computational complexity of functions are often expressed with asymptotic notation. Some common forms of asymptotic notion of functions are \Omega(T(n)) and \Theta(T(n)). > \Theta(T(n)) expresses that something is bounded above by cT(n) where c is a constant such that c>0 and T(n) is a function of n, \Omega(T(n)) expresses that something is bounded below by cT(n) where c is a constant such that c>0 and T(n) is a function of n, and \Theta(T(n)) expresses both O(T(n)) and \Omega(T(n)). [3] These notations also their own names. O(T(n)) is called Big O notation, \Omega(T(n)) is called Big Omega notation, and \Theta(T(n)) is called Big Theta notation. Quantum complexity theory > Simulation of quantum circuits https://en.wikipedia.org/wiki/Quantum_complexity_theory#Simulation_of_quantum_circuits https://en.wikipedia.org/wiki/Quantum_complexity_theory#Simu... : > There is no known way to efficiently simulate a quantum computational model with a classical computer. This means that a classical computer cannot simulate a quantum computational model in polynomial time [P]. However, a quantum circuit of S(n) qubits with T(n) quantum gates can be simulated by a classical circuit with O(2^{S(n)}T(n)^{3}) classical gates. [3] This number of classical gates is obtained by determining how many bit operations are necessary to simulate the quantum circuit. In order to do this, first the amplitudes associated with the S(n) qubits must be accounted for. Each of the states of the S(n) qubits can be described by a two-dimensional complex vector, or a state vector. These state vectors can also be described a linear combination of its component vectors with coefficients called amplitudes. These amplitudes are complex numbers which are normalized to one, meaning the sum of the squares of the absolute values of the amplitudes must be one. [3] The entries of the state vector are these amplitudes. Quantum Turing machine: https://en.wikipedia.org/wiki/Quantum_Turing_machine https://en.wikipedia.org/wiki/Quantum_Turing_machine Quantum circuit: https://en.wikipedia.org/wiki/Quantum_circuit https://en.wikipedia.org/wiki/Quantum_circuit Church-Turing-Deutsch principle: https://en.wikipedia.org/wiki/Church%E2%80%93Turing%E2%80%93Deutsch_principle https://en.wikipedia.org/wiki/Church%E2%80%93Turing%E2%80%93... Computational complexity > Quantum computing, Distributed computing: https://en.wikipedia.org/wiki/Computational_complexity#Quantum_computing https://en.wikipedia.org/wiki/Computational_complexity#Quant...